Algorithm analysis - Data Structures and Problem Solving Using Java - page 200

figure 5.8
A linear maximum
contiguous
subsequence sum
algorithm

1 /**
2 * Linear maximum contiguous subsequence sum algorithm.
3 * seqStart and seqEnd represent the actual best sequence.
4 */
5 public static int maximumSubsequenceSum( int [ ] a )
6 {
7 int maxSum = 0;
8 int thisSum = 0;
9
10 for( int i = 0, j = 0; j < a.length; j++ )
11 {
12 thisSum += a[ j ];
13
14 if( thisSum > maxSum )
15 {
16 maxSum = thisSum;
17 seqStart = i;
18 seqEnd = j;
19 }
20 else if( thisSum < 0 )
21 {
22 i = j + 1;
23 thisSum = 0;
24 }
25 }
26
27 return maxSum;
28 }

Theorem 5.3 tells us that, when a negative subsequence is detected, not
only can we break the inner loop, but also we can advance i to j+1 . Figure 5.8
shows that we can rewrite the algorithm using only a single loop. Clearly, the
running time of this algorithm is linear: At each step in the loop, we advance
j , so the loop iterates at most N times. The correctness of this algorithm is
much less obvious than for the previous algorithms, which is typical. That is,
algorithms that use the structure of a problem to beat an exhaustive search
generally require some sort of correctness proof. We proved that the algorithm
(although not the resulting Java program) is correct using a short mathemati-
cal argument. The purpose is not to make the discussion entirely mathemati-
cal, but rather to give a flavor of the techniques that might be required in
advanced work.

If we detect a neg-
ative sum, we can
move i all the way
past j .

If an algorithm is
complex, a correct-
ness proof is
required.