# Help on understanding the proof for the max subsequence problem

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}$

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?

-

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.
+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
All the picture purports to show is that $S_{p,q}\le S_i,q$ –  deinst Nov 27 '11 at 19:38