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

figure 5.5
A quadratic maximum
contiguous
subsequence sum
algorithm

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

Let A ij be any sequence with S ij < 0 . If qj > , then A iq is not the maximum con-

Theorem 5.2

, , ,

tiguous subsequence.

Proof

The sum of A 's elements from i to q is the sum of A 's elements from i to j added to
the sum of A 's elements from j + 1 to q . Thus we have S iq = S ij + S j . Because

, , + 1 q ,

S ij < 0 , we know that S iq < S j . Thus A iq is not a maximum contiguous subse-

, , + 1 , q ,

quence.

An illustration of the sums generated by i , j , and q is shown on the first
two lines in Figure 5.6. Theorem 5.2 demonstrates that we can avoid examin-
ing several subsequences by including an additional test: If thisSum is less
than 0, we can break from the inner loop in Figure 5.5. Intuitively, if a subse-
quence's sum is negative, then it cannot be part of the maximum contiguous
subsequence. The reason is that we can get a larger contiguous subsequence