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]}")