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 low
and 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?