Exercise 4.1.2

Write pseudocode for the brute-force method of solving the maximum-subarray problem. Your procedure should run in $\Theta(n^2)$ time.

FIND-MAX-SUBARRAY(A, low, high)
  left = 0
  right = 0
  sum = -∞
  for i = low to high
      current-sum = 0
      for j = i to high
      current-sum += A[j]
      if sum < current-sum
          sum = current-sum
      left = i
      right = j
  return (left, right, sum)