Max Subsequence Problem

• Given a sequence of integers A1, A2, …, An, find the

maximum possible sum value of a subsequence Ai, …, Aj.
Algorithm Analysis • Numbers can be negative.
• You want a contiguous chunk with largest sum.
Example: Max Subsequence Problem
• Example: -2, 11, -4, 13, -5, -2
• The answer is 20 (subseq. A2 through A4).
Fitsum Admasu
Department of Computer Science • We will discuss 4 different algorithms, with different time
Addis Ababa University complexities.

Algorithm 1 for Max Subsequence Sum Algorithm 1 for Max Subsequence Sum
• Given A1,…,An , find the maximum value of Ai+Ai+1+···+Aj • Given A1,…,An , find the maximum value of Ai+Ai+1+···+Aj
0 if the max value is negative 0 if the max value is negative

int maxSum = 0; int maxSum = 0; O (1)

for( int i = 0; i < a.size( ); i++ ) for( int i = 0; i < a.size( ); i++ )
for( int j = i; j < a.size( ); j++ ) for( int j = i; j < a.size( ); j++ )
{ { O (1)
int thisSum = 0; int thisSum = 0; n -1 n -1
O(å å ( j - i + 1))
n -1
for( int k = i; k <= j; k++ ) for( int k = i; k <= j; k++ ) O( j - i + 1) O(å ( j - i + 1))
i= 0 j =i
thisSum += a[ k ]; thisSum += a[ k ]; O (1) j =i

if( thisSum > maxSum ) if( thisSum > maxSum )

maxSum = thisSum; maxSum = thisSum; O (1)
} }
return maxSum; return maxSum;

Overall time complexity for Algo 1 is O(n3)

3 4

Algorithm 1 Analysis Algorithm 2 for Max Subsequence Sum

• Idea: Given sum from i to j-1, we can compute the sum from i
Inner loop: to j in constant time.
åj=in-1 (j-i + 1) = (n – i + 1)(n-i)/2 • This eliminates one nested loop, and reduces the running time
to O(n2).
Note: From mathematics, series and summation:
1 + 2 + 3 + ……. n = n(n+1)/2 (arithmetic series) into maxSum = 0;

for( int i = 0; i < a.size( ); i++ )

Outer Loop: int thisSum = 0;
for( int j = i; j < a.size( ); j++ )
åi=0n-1 (n – i + 1)(n-i)/2 = (n3 + 3n2 + 2n)/6 {
thisSum += a[ j ];
Note: From mathematics, Sum of squares: if( thisSum > maxSum )
1 + 22 + 32 +………n2 = n(n + 1)(2n + 1)/6 maxSum = thisSum;
}
Overall time complexity for Algo 1 is O(n3) return maxSum;
For detail proof: refer to chapter 2 of Mark Allen Weiss,”Data Structures and Algorithms 6
analysis in C++”; second edition
 Algorithm 2 for Max Subsequence Sum Algorithm 3 for Max Subsequence Sum
• Idea: Given sum from i to j-1, we can compute the sum from i
• This algorithm uses divide-and-conquer paradigm
to j in constant time.
– Break a big problem into two small sub-problems
• This eliminates one nested loop, and reduces the running time – Solve each of them efficiently.
to O(n2). – Combine the two solutions
into maxSum = 0; • Suppose we split the input sequence at midpoint.
– Divide the array into two parts: left part, right part
for( int i = 0; i < a.size( ); i++ ) Time complexity: O(n2) – The max subsequence is entirely in the left half, entirely in the right half, or it
int thisSum = 0; spans the middle.
for( int j = i; j < a.size( ); j++ ) – If it spans the middle, then it includes the max subsequence in the left ending at
{
thisSum += a[ j ];
åi=0n-1 (n-i) = (n2 – n)/2 the last element and the max subsequence in the right starting from the center
if( thisSum > maxSum ) • Example: left half | right half
maxSum = thisSum; 4 -3 5 -2 | -1 2 6 -2
} • Max in left is 6 (A1 through A3); max in right is 8 (A6 through A7). But
return maxSum;
max subsequence sum spanning the middle is 11 (A1 thru A7).
7
8

Algorithm 3 for Max Subsequence Sum (cont.) Algorithm 3 for Max Subsequence Sum (cont.)
Maxsubsum(A[], left, right)
• Example: { if (left = right) return (maxsum = max(A[left], 0));
left half | right half Center = ë (left + right)/2û ; // floor function - the maximum integer
4 -3 5 -2 | -1 2 6 -2 maxleftsum = Maxsubsum(A[],left, center);
• Max subsequences in each half found by recursion. maxrightsum = Maxsubsum(A[],center+1,right);
• How do we find the spanning max subsequence? maxleftbordersum = 0; leftbordersum = 0;
• Key Observation: for (i=center; i>=left; i--)
– Left half of the spanning sequence is the max subsequence ending with leftbordersum+=A[i];
-2. maxleftbordersum = max(maxleftbordersum, leftbordersum);
– Right half is the max subsequence beginning with -1. maxrightbordersum = 0; rightbordersum = 0;
for (i=center+1; i<=right; i++)
• A linear scan lets us compute these in O(n) time. rightbordersum+=A[i];
maxlrightbordersum = max(maxleftbordersum, leftbordersum);
return(max(maxleftsum, maxrightsum, maxrightbordersum + maxleftbordersum));
9 }

Algorithm 3 for Max Subsequence Sum (cont.) Algorithm 4 for Max Subsequence Sum

• The divide and conquer is best analyzed through recurrence: • Max subsequence cannot start or end at a negative Ai.
T(1) = 1 • More generally, the max subsequence cannot have a prefix
T(n) = 2T(n/2) + O(n) with a negative sum.
= 2.cn/2 + 4T(n/4) + cn Ex: -2 11 -4 13 -5 -2
= 4T(n/4) + 2cn • Thus, if we ever find that Ai through Aj sums to < 0, then we
= 8T(n/8) + 3cn can advance i to j+1
=…………..
– Proof.
= 2iT(n/2i) + icn
• Suppose j is the first index after i when the sum becomes < 0
=………………… (reach a point when n = 2i i=log n
• The max subsequence cannot start at any p between i and j.
= n.T(1) + cnlogn
Because Ai through Ap-1 is positive, so starting at i would have been
= O(nlogn) even better.
• Therefore, algorithm 3 has O(n log n) time complexity.
11 12
 Algorithm 4 for Max Subsequence Sum Algorithm 4 for Max Subsequence Sum

int maxSum = 0, thisSum = 0; int maxSum = 0, thisSum = 0;

for( int j = 0; j < a.size( ); j++ ) for( int j = 0; j < a.size( ); j++ )
{ {
thisSum += a[ j ]; thisSum += a[ j ];

if ( thisSum > maxSum ) if ( thisSum > maxSum )

maxSum = thisSum; maxSum = thisSum; • Time complexity O(n)
else if ( thisSum < 0 ) else if ( thisSum < 0 )
thisSum = 0; thisSum = 0;
} }
return maxSum return maxSum

• The algorithm resets whenever thisSum is < 0. Otherwise, it • The algorithm resets whenever thisSum is < 0. Otherwise, it
forms new sums and updates maxSum in one pass. forms new sums and updates maxSum in one pass.
14
13

Summary for Max Subsequence Problem Summary for Max Subsequence Problem

• We have discussed 4 different algorithms, with time

complexities O(n3), O(n2), O(n log n), and O(n).

Plot (n vs. seconds) of various maximum subsequence sum algorithms

Plot (n vs. milliseconds) of various maximum subsequence sum algorithms
15
With n = 106, algorithm 1 may take > 1 year; algorithm 4 will
take a fraction of a second!