Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to understand a proof.

The problem is the detection of the maximum continuous subsequence sum problem (i.e. find the subsequence of an array that gives the maximum sum).

The algorithm for O(N) is based on the following observation, which part of it I can not follow and I ask here:

For any $i$, $A_{i,j}$ let be the first sequence, with $S_{i,j} < 0$ . Then, for any $i\le p \le j$ and $p \le q$, $A_{p,q}$ either is not a maximum contiguous subsequence or is equal to an already seen maximum contiguous subsequence.

The proof for this is based on the following:

....We have $S_{i,q}=S_{i,p-1}+S_{p,q}$. Since $j$ is the lowest index for which $S_{i,j} <0$, it follows that $S_{i,p-1}\ge 0$. Thus $S_{p,q} \le S_{i,q}$

MaxSumProof

I don't see why $S_{i,p-1}$ is $\le 0$.
I see that $S_{i,j}= S_{i,p-1}+S_{p,j}$ but how we conclude that $S_{i,p-1}$ is the nonnegative part, I can not understand.
Any help on this please?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

You have that $p-1<j$ if $S_{i,p-1} < 0$ then $j$ would not be the first index such that $S_{i,j}<0$, $p-1$ (or something smaller would be the smallest index. If $S_{i,p-1}$ is not less than 0 then it must be greater than or equal to 0.

Note: You should define your variables, from context, I can guess that $S_{i,j}$ is the sum of the numbers from $i$ to $j$, but I should not have to guess.

share|improve this answer
    
+1.So I did not fully understand the statement Aij let be the first sequence, with Sij<0? Essentially it means that any index prior to j (so p-1 here) can no be summing to negative, right? Yes you are right it is the sum of the numbers from i to j. I am sorry I was not clear on this.Thank you for your time –  user384706 Nov 27 '11 at 18:00
    
Yes, it means that no prior index has a negative sum. –  deinst Nov 27 '11 at 18:05
    
The 2 boxes in the picture seem to imply that the Si,q is the same sum regardless if q is greater or smaller than j.How is this possible? –  user384706 Nov 27 '11 at 18:56
    
All the picture purports to show is that $S_{p,q}\le S_i,q$ –  deinst Nov 27 '11 at 19:38
    
Thanks for your help!Got it now –  user384706 Nov 27 '11 at 20:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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