Finding a maximum subarray in worst-case linear time

Question

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?

Answer 1

sum computes the value of maximum subarray of the form $A[i..j+1]$. And, currentlow is $i$ and currenthigh is $j+1$. Note that currenthigh is incrementing in every iteration by 1ドル$ that means it is pointing to current $j$ always.

If sum>0 (value of maximum subarray of the form $A[i..j]$), then it is always better to make new-sum = sum + A[j+1] because then sum + A[j+1] > A[j+1,j+1] irrespective of whether $A[j+1]$ is negative or positive. Here, new-sum: value of maximum subarray of the form $A[i..j+1]$.

Similarly, if sum<0, then it is always better to make the new-sum = A[j+1,j+1] because sum + A[j+1] < A[j+1][j+1] irrespective of whether $A[j+1]$ is negative or positive.

Therefore, the correct sum is computed in the first if else statement.

After that, you are right that max-sum is the value of maximum subarray of $A[1,j+1]$. And, low and high are its indices. Note that they do not change unless sum > max-sum that should be the case as per the DP method.