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

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
    +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 time2011-11-27
  • 0
    Yes, it means that no prior index has a negative sum.2011-11-27
  • 0
    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?2011-11-27
  • 0
    All the picture purports to show is that $S_{p,q}\le S_i,q$2011-11-27
  • 0
    Thanks for your help!Got it now2011-11-27