Here's a problem of CLRS:
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[1..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 subarray ending at index $j$.
Now this is a solution to it:
ITERATIVE-FIND-MAXIMUM-SUBARRAY(A) n = A.length max-sum = -∞ sum = -∞ for j = 1 to n: currentHigh = j if sum > 0: sum = sum + A[j] else currentLow = j sum = A[j] if sum > max-sum: max-sum = sum low = currentLow high = currentHigh return (low, high, max-sum)
I understand how
max-sum is indeed the sum of a maximum subarray but I can't figure out how
high are the indices of such a subarray. I don't know what the procedure is and how it updates these variables in each iteration. Any ideas?