# Finding a maximum subarray in worst-case linear time

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?

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.