| Prev | Next |
Maximum Sum Subsequence
Consider the string A[1..n] of both positive and negative integers. The goal is to find the subsequence in A with the maximum sum.
Example
A[1..8] = {2, -4, 1, 9, -6, 7 -5, 3}. The subsequence with maximum sum is {2, 1, 9, 7, 3} and the sum is 22.
(1) Brute-force solution
The brute-force way to solve this problem is to enumerate all possible subsequences and determine the one that has the maximum sum. For n elements, there are 2n subsequences possible.
The brute-force solution can be implemented using recursion given as follows. Let MSS(1..n) denote the length of the longest palindromic subsequence for S.
MSS(A[1..n]) {
if (n == 0)
return 0;
sum1 = MSS(A[1..n-1]);
sum2 = MSS(A[1..n-1]) + A[n];
return max(sum1, sum2);
}
The recursion tree is shown below. Each call path from the root to the leaf gives one of the 2n possible subsequences. Let MSS(1,n) denote the maximum sum subsequence of the A[1..n].
MSS(1,n)
|
|
---------------------------max---------------------------
| |
| |
MSS(1,n-1) MSS(1,n-1) + A[n]
| |
| |
-----------max--------- ----------max----------
| | | |
| | | |
MSS(1,n-2) MSS(1,n-2) + A[n-1] MSS(1,n-2) MSS(1,n-2) + A[n-1]
: : : :
: : : :
Time complexity
The recursive solution takes O(2n) time.
(2) Greedy Solution
To apply greedy strategy we need to first check if the problem exhibits (i) optimal substructure property and (ii) greedy choice property.
Optimal substructure: The recursive fomulation above reveals the optimal substructure. The problem of finding maximum sum subsequence of A[1..n] contains within itself the subproblem of finding maximum sum subsequence of A[1..n-1].
Greedy choice property: To check if a greedy solution exists or not, we need to determine if greedy choice property is satisfied. i.e. do we have any way to decide which of the 2 subproblems need to be solved at each recursive step?
Yes. We can make a clear choice by checking if the element A[i] is positive or not. If A[i] > 0, it helps improve the sum. So we can take the right path which includes A[i]. Else, we can take the left path which excludes A[i]. The recurrence equation for the greedy version reduces to
T(n) = T(n-1) + 1 = O(n)
We initially start with sum = 0 and scan though the elements. If an element is > 0, we will add the element to the sum. After scan is complete we return the sum. Checking if the element is > 0 takes O(1) time while the number of iterations is n.
There is one corner case to be dealt with. If all the elements happen to be negative, as per our strategy no element will be picked. In this case the answer should be the max element.
The greedy solution can be implemented in an iterative fashion as follows.
GreedyMSS(A[1..n]) {
int maxsubsum = 0;
for (i = 1; i <= n; i++) {
if (A[i] > 0)
maxsubsum += A[i];
}
if (maxsubsum != 0)
return maxsubsum;
else // i.e. all elements are negative
return findMax(A[1..n]);
}
(3) Dynamic Programming Solution
If the greedy solution exists, dynamic programming solution is not necessary. However, we discuss the dynamic programming solution below.
To apply dynamic programming, we need to check if the problem exhibits (i) optimal substructure and (ii) overlapping subproblems properties.
(i) We already saw above, that optimal substructure property holds.
(ii) The recursive formulation also reveals the existence of overlapping subproblems doubles at each step and therefore exponential subproblems are possible.
The dynamic programming works in a bottom-up fashion. Subproblems are solved and their solutions are used to find solutions to larger problems. Hence, we work as follows.
- If we are allowed to pick each element individually, what is the maximum subsequence sum possible?
- If we are allowed to pick two consecutive elements, what is the maximum subsequence sum possible?
- So on and so forth ... until all elements are allowed to be picked.
Let MSS[i,j] denote the maximum subsequence sum for array A[i..j]. Initially, j = i. In the subsequent iterations, j takes the values of (i+1), (i+2), ..., (i+n-1). This can be consolidated by defining a special variable 'len' which takes values 0 through n-1 denoting the length of consecutive tasks considered for that iteration. And hence, j = i + len for len = 0...n-1.
- In the first iteration len = 0, we find the max subsequence sum for the range [i,i].
i.e. MSS[1,1], MSS[2,2], ..., MSS[n,n]. (n computations) - In the second iteration len = 1, we find the max subsequence sum for the range [i,i+1].
i.e. MSS[1,2], MSS[2,3], ..., MSS[n-1,n]. (n-1 computations) - In the third iteration len = 2, we find the max subsequence sum for the range [i,i+2].
i.e. MSS[1,3], MSS[2,4], ..., MSS[n-2,n]. (n-2 computations) - ....
- ....
- In the last but one iteration len = n-2, we find the max subsequence sum for the range [i,i+n-2].
i.e. MSS[1,n-1], MSS[2,n] (2 computations) - In the last (nth) iteration len = n-1, we find the max subsequence sum for [i,i+n-1].
i.e. MSS[1,n]. (1 computation)
The entire computation worked out above can be accomplished using the following nested loop.
for (len = 0; len < n; len++) {
for (i = 1; i <= n-len; i++) {
j = i + len
// Determine MSS[i,j]
.............
.............
}
}
Now we will focus on the computation of MSS[i,j].
Iteration 1: len = 0; i = 1 to n; j = i+len = i;
Each element considered individually is its own sum. i.e. MSS[i,i] = A[i].
For the given example.
A[1] = 2 --> MSS[1,1] = 2
A[2] = -4 --> MSS[2,2] = -4
A[3] = 1 --> MSS[3,3] = 1
A[4] = 9 --> MSS[4,4] = 9
A[5] = -6 --> MSS[5,5] = -6
A[6] = 7 --> MSS[6,6] = 7
A[7] = -5 --> MSS[6,6] = -5
A[8] = 3 --> MSS[6,6] = 3
| i \ j |
j = 1 | j = 2 | j = 3 | j = 4 | j = 5 | j = 6 | j = 7 | j = 8 |
| i = 1 | MSS[1,1] = 2 |
|||||||
| i = 2 | MSS[2,2] = -4 |
|||||||
| i = 3 | MSS[3,3] = 1 |
|||||||
| i = 4 | MSS[4,4] = 9 |
|||||||
| i = 5 | MSS[5,5] = -6 |
|||||||
| i = 6 | MSS[6,6] = 7 |
|||||||
| i = 7 | MSS[7,7] = -5 |
|||||||
| i = 8 | MSS[8,8] = 3 |
Iteration 2: len = 1; i = 1 to n-1; j = i+len = i+1;
Maximum subsequence sum for 2 contiguous elements MSS[i,i+1] is bigger of MSS[i,i], MSS[i+1,i+1] or sum of both.
For the given example.
A[1..2] = {2, -4} --> MSS[1,2] = max{MSS[1,1], MSS[2,2], MSS[1,1]+MSS[2,2]} = max{2,-4,-2} = 2
A[2..3] = {-4, 1} --> MSS[2,3] = max{MSS[2,2], MSS[3,3], MSS[2,2]+MSS[3,3]} = max{-4,1,-3} = 1
A[3..4] = {1, 9} --> MSS[3,4] = max{MSS[3,3], MSS[4,4], MSS[3,3]+MSS[4,4]} = max{1,9,10} = 10
A[4..5] = {9, -6} --> MSS[4,5] = max{MSS[4,4], MSS[5,5], MSS[4,4]+MSS[5,5]} = max{9,-6,3} = 9
A[5..6] = {-6, 7} --> MSS[5,6] = max{MSS[5,5], MSS[6,6], MSS[5,5]+MSS[6,6]} = max{-6,7,1} = 7
A[6..7] = {7, -5} --> MSS[6,7] = max{MSS[6,6], MSS[7,7], MSS[6,6]+MSS[7,7]} = max{7,-5,2} = 7
A[7..8] = {-5, 3} --> MSS[7,8] = max{MSS[7,7], MSS[8,8], MSS[7,7]+MSS[8,8]} = max{-5,3,-2} = 3
| i \ j |
j = 1 | j = 2 | j = 3 | j = 4 | j = 5 | j = 6 | j = 7 | j = 8 |
| i = 1 | MSS[1,1] = 2 |
MSS[1,2] = 2 |
||||||
| i = 2 | MSS[2,2] = -4 |
MSS[2,3] = 1 |
||||||
| i = 3 | MSS[3,3] = 1 |
MSS[3,4] = 10 |
||||||
| i = 4 | MSS[4,4] = 9 |
MSS[4,5] = 9 |
||||||
| i = 5 | MSS[5,5] = -6 |
MSS[5,6] = 7 |
||||||
| i = 6 | MSS[6,6] = 7 |
MSS[6,7] = 7 |
||||||
| i = 7 | MSS[7,7] = -5 |
MSS[7,8] = 3 |
||||||
| i = 8 | MSS[8,8] = 3 |
Iteration 3~n: len = 2 to n-len; i = 1 to n-len; j = i+len;
Maximum subsequence sum for MSS[i,j] is bigger of MSS[i,k], MSS[k+1,j], MSS[i,k] + MSS[k+1,j] where k = i to j-1.
MSS[i,j] = max {
MSS[i,i], MSS[i+1,j], MSS[i,i]+MSS[i+1,j],
MSS[i,i+1], MSS[i+2,j], MSS[i,i+1]+MSS[i+2,j],
...........,
...........,
MSS[i,j-2], MSS[j-1,j], MSS[i,j-2]+MSS[j-1,j],
MSS[i,j-1], MSS[j,j], MSS[i,j-1]+MSS[j,j]
}
To elaborate this further, consider the particular case of computing MSS[1,3]. Practically, it could be any one of the following 7 possibilities: A[1], A[2], A[3], A[1]+A[2], A[2]+A[3], A[1]+A[3], A[1]+A[2]+A[3]. The 7 possibilities can be represented using one of the following 6 options.
- A[1] > 0 and A[2], A[3] < 0. MSS[1,1] represents this possibility.
- A[1] < 0 and either A[2] or A[3] or both > 0. MSS[2,3] represents this possibility.
- A[1] > 0 and either A[2] or A[3] or both > 0. MSS[1,1] + MSS[2,3] represents this possibility.
- Either A[1] or A[2] or both > 0 and A[3] < 0. MSS[1,2] represents this possibility.
- A[1], A[2] < 0 and A[3] > 0. MSS[3,3] represents this possibility.
- Either A[1] or A[2] or both > 0 and A[3] > 0. MSS[1,2] + MSS[3,3] represents this possibility.
Consequently,
- For i = 1 and j = 3 (meaning len = 2), k assumes two values 1 and 2.
MSS[1,3] = max {
MSS[1,1], MSS[2,3], MSS[1,1]+MSS[2,3],
MSS[1,2], MSS[3,3], MSS[1,2]+MSS[3,3]
}
In a similar vein,
- For i = 1 and j = 4 (meaning len = 3), k assumes three values 1, 2 and 3.
- For i = 1 and j = 5 (meaning len = 4), k assumes three values 1, 2, 3 and 4.
MSS[1,4] = max {
MSS[1,1], MSS[2,4], MSS[1,1]+MSS[2,4],
MSS[1,2], MSS[3,4], MSS[1,2]+MSS[3,4],
MSS[1,3], MSS[4,4], MSS[1,3]+MSS[4,4]
}
MSS[1,4] = max {
MSS[1,1], MSS[2,5], MSS[1,1]+MSS[2,5],
MSS[1,2], MSS[3,5], MSS[1,2]+MSS[3,5],
MSS[1,3], MSS[4,5], MSS[1,3]+MSS[4,5]
MSS[1,4], MSS[5,5], MSS[1,4]+MSS[5,5]
}
It can be seen that, as len increases, the gap between i and j widens, forcing k to assume wider range of values. In fact, this computation can extended to iteration 2 also where k takes exactly one value i. The computation can be generalized by using an innermost loop as follows.
for (len = 1; len < n; len++) { // From iteration 2
for (i = 1; i <= n-len; i++) {
j = i + len
for (k = i; k <= j-1; k++)
MSS[i,j] = max{ MSS[i,k], MSS[k+1,j], MSS[i,k]+MSS[k+1,j] }
}
}
The completed table based on the above generalization is given below.
| i \ j |
j = 1 | j = 2 | j = 3 | j = 4 | j = 5 | j = 6 | j = 7 | j = 8 |
| i = 1 | MSS[1,1] = 2 |
MSS[1,2] = 2 |
MSS[1,3] = 3 |
MSS[1,4] = 12 |
MSS[1,5] = 12 |
MSS[1,6] = 19 |
MSS[1,7] = 19 |
MSS[1,8] = 22 |
| i = 2 | MSS[2,2] = -4 |
MSS[2,3] = 1 |
MSS[2,4] = 10 |
MSS[2,5] = 10 |
MSS[2,6] = 17 |
MSS[2,7] = 17 |
MSS[2,8] = 20 |
|
| i = 3 | MSS[3,3] = 1 |
MSS[3,4] = 10 |
MSS[3,5] = 10 |
MSS[3,6] = 17 |
MSS[3,7] = 17 |
MSS[3,8] = 20 |
||
| i = 4 | MSS[4,4] = 9 |
MSS[4,5] = 9 |
MSS[4,6] = 16 |
MSS[4,7] = 16 |
MSS[4,8] = 19 |
|||
| i = 5 | MSS[5,5] = -6 |
MSS[5,6] = 7 |
MSS[5,7] = 7 |
MSS[5,8] = 10 |
||||
| i = 6 | MSS[6,6] = 7 |
MSS[6,7] = 7 |
MSS[6,8] = 10 |
|||||
| i = 7 | MSS[7,7] = -5 |
MSS[7,8] = 3 |
||||||
| i = 8 | MSS[8,8] = 3 |
Algorithm
The dynamic programming algorithm for maximum subsequence sum is given as follows.
int MSS[1..n][1..n];
DPMSS(int A[1..n]) {
for (i = 1; i <= n; i++)
MSS[i][i] = A[i];
for (len = 1; len < n; len++) {
for (i = 1; i <= n-len; i++) {
j = i + len;
for (k = i; k <= j-1; k ++)
MSS[i,j] = max( MSS[i,k], MSS[k+1,j], MSS[i,k]+MSS[k+1,j] );
}
}
return MSS[1][n];
}
Time complexity
There are 3 loops. The outerloop runs for n-1 times. The inner loop runs for at most n-1 times. The innermost loop runs for at most n-1 times. Thus, the time complexity is O(n3).
(4) Divide-and-Conquer Solution
This problem has a divide-and-conquer solution too. The basic idea is to split the array into almost equal halves recursively until there exists only one element. While merging pick the bigger of the three quantities: MSS[1..n/2], MSS{n/2+1..n], MSS[1..n/2]+MSS{n/2+1..n].
For the given example,
{2, -4, 1, 9, -6, 7 -5, 3}
|
|
-----------------------------------------------------
| |
| |
{2, -4, 1, 9} {-6, 7, -5, 3}
--------------------------- -----------------------------
| | | |
| | | |
{2, -4} {1, 9} {-6, 7} {-5, 3}
| | | |
| | | |
--------------- -------------- -------------- ---------------
| | | | | | | |
| | | | | | | |
{2} {-4} {1} {9} {-6} {7} {-5} {3}
..............................DIVIDE PHASE OVER....START CONQUERING...............................
2 -4 1 9 -6 7 -5 3
| | | | | | | |
| | | | | | | |
--------------- -------------- -------------- ---------------
| | | |
| | | |
2 10 7 3
| | | |
| | | |
--------------------------- -----------------------------
| |
| |
12 10
| |
| |
-----------------------------------------------------
|
|
22
Algorithm
The divide-and-conquer algorithm for maximum subsequence sum is given as follows.
DCMSS(int A[1..n]) {
if (n == 1)
return A[1];
mss1 = DCMSS(A[1..n/2]);
mss2 = DCMSS(A[n/2+1..n]);
return max(mss1, mss2, mss1+mss2);
}
Time complexity
There depth of the recursion tree is logn. Divide phase requires O(1) operation. During the conquer phase, at most n/2 comparisons are done. Hence, the time complexity is O(nlogn).