Write pseudocode for the brute-force method of solving the maximum-subarray problem. Your procedure should run in \(\Theta(n^2)\) time.
$$\textsc {Find-Maximum-Subarray-BruteForce }(A, low, high)$$$$\begin{aligned}1& \quad left=low \\2& \quad right=high \\3& \quad sum=-∞ \\4& \quad \textbf {for }i=low\textbf { to }high \\5& \quad \qquad tempSum=0 \\6& \quad \qquad \textbf {for }j=i\textbf { to }high \\7& \quad \qquad \qquad tempSum=tempSum+A[j] \\8& \quad \qquad \qquad \textbf {if }tempSum>sum \\9& \quad \qquad \qquad \qquad sum=tempSum \\10& \quad \qquad \qquad \qquad left=i \\11& \quad \qquad \qquad \qquad right=j \\12& \quad \textbf {return }\textsc {}(left,\,right,\,sum) \\\end{aligned}$$
You can find Python implementation of this at the bottom of the page.
Python implementation
import math
def FindMaxSubarrayBruteForce(A, low, high):
left = low
right = high
sum = -math.inf
for i in range(low, high):
tempSum = 0
for j in range(i, high):
tempSum = tempSum + A[j]
if tempSum > sum:
sum = tempSum
left = i
right = j
return (left, right, sum)
# Test with exact same array as in the example give in book
# Expected answer is A[8..11] = 43
arr = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
ans = FindMaxSubarrayBruteForce(arr, 0, len(arr))
print(f"Max subarray = A[{ans[0] + 1}..{ans[1] + 1}] = {ans[2]}")