1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.