0
$\begingroup$

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?

1 Answers 1

1

You have that $p-1 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.

  • 0
    Thanks for your help!Got it now2011-11-27