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?