Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of \(A[1..j]\), extend the answer to find a maximum subarray ending at index \(j+1\) by using the following observation: a maximum subarray of \([A..j+1]\) is either a maximum subarray of \(A[1..j]\) or a subarray \(A[i..j+1]\), for some \(1 \leq i \leq j + 1\). Determine a maximum subarray of the form \(A[i..j+1]\) in constant time based on knowing a maximum subarrray ending at index \(j\).

NONRECURSIVE LINEAR-TIME FIND-MAXIMUM-SUBARRAY(A)

01 low = 0

02 temp-low = 1

03 high = 0

04 temp-sum = 0

05 sum = 0

06 for i = 1 to A.length

07      temp-sum = MAX(A[i], temp-sum + A[i])

08      if temp-sum > sum

09          sum = temp-sum

10          low = temp-low

11          high = i

12      if temp-sum == A[i]

13          temp-low = i

14 return (low, high, sum)

They secret sauce with this algorithm is setting the new temp-low upon finding an \(A[i]\) that is larger than the current temp-sum. This only happens when the preceding elementes in \(A\) are too negative to be able to be a part of our new maximum subarray and so when this occurs we reset the beginning of our new possible maximum-subarray, but do not actually record it unless we see temp-sum overtake our current recorded sum.