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\,=\,-\infty \\
4& \quad \textbf{for }\,i\,=\,low\textbf{ to }\,high \\
5& \quad \qquad temp\text{-}sum\,=\,0 \\
6& \quad \qquad \textbf{for }\,j\,=\,i\textbf{ to }\,high \\
7& \quad \qquad \qquad temp\text{-}sum\,=\,temp\text{-}sum\,+\,A[j] \\
8& \quad \qquad \qquad \textbf{if }\,temp\text{-}sum\,>\,sum \\
9& \quad \qquad \qquad \qquad sum\,=\,temp\text{-}sum \\
10& \quad \qquad \qquad \qquad left\,=\,i \\
11& \quad \qquad \qquad \qquad right\,=\,j \\
12& \quad \textbf{return }\,(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]}")