Find a subsequence of a given sequence such that subsequence sum is as high as possible and subsequence’s elements are in sorted order, from lowest to highest. This subsequence is not necessarily contiguous, or unique.

For example, consider the subsequence [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11]. The maximum sum increasing subsequence is [8 12 14] which has sum 34

The Maximum sum increasing subsequence (MSIS) problem is a standard variation of Longest Increasing Subsequence problem.

The idea is to use Recursion to solve this problem. For each item, there are two possibilities –

2. We exclude current item from MSIS and recurse for remaining items.

Finally, we return maximum sum we get by including or excluding current item. The base case of the recursion would be when no items are left.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <climits> using namespace std; // Function to find maximum sum of increasing subsequence int MSIS(int arr[], int i, int n, int prev, int sum) { // Base case: nothing is remaining if (i == n) return sum; // case 1: exclude the current element and process the // remaining elements int excl = MSIS(arr, i + 1, n, prev, sum); // case 2: include the current element if it is greater // than previous element int incl = sum; if (arr[i] > prev) incl = MSIS(arr, i + 1, n, arr[i], sum + arr[i]); // return maximum of above two choices return max(incl, excl); } // main function int main() { int arr[] = { 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Maximum sum of increasing subsequence is " << MSIS(arr, 0, n, INT_MIN, 0); return 0; } |

`Output:`

Maximum sum of increasing subsequence is 34

The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

The problem has an optimal substructure. That means the problem can be broken down into smaller, simple “subproblems”, which can further be divided into yet simpler, smaller subproblems until the solution becomes trivial. Above solution also exhibits overlapping subproblems. If we draw the recursion tree of the solution, we can see that the same sub-problems are getting computed again and again.

We know that problems having optimal substructure and overlapping subproblems can be solved by using **Dynamic Programming**, in which subproblem solutions are *Memo*ized rather than computed again and again. The *Memo*ized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values.

We can also solve this problem in bottom-up manner. In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them. The following bottom-up approach computes sum[i], for each 0 <= i < n, which stores the maximum sum of an increasing subsequence of subarray arr[0..i] that ends with arr[i]. To calculate sum[i], we consider MSIS of all smaller values of i (say j) already computed and pick the maximum sum[j] where arr[j] is less than the current element arr[i] and add current element arr[i] to it. It has the same asymptotic run-time as Memoization but no recursion overhead.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <climits> using namespace std; // Iterative function to find maximum sum of an increasing subsequence int MSIS(int arr[], int n) { // array to store sub-problem solution. sum[i] stores the maximum // sum of the increasing subsequence that ends with arr[i] int sum[n] = { 0 }; // base case sum[0] = arr[0]; // start from second element in the array for (int i = 1; i < n; i++) { // do for each element in subarray arr[0..i-1] for (int j = 0; j < i; j++) { // find increasing subsequence with maximum sum that ends with // arr[j] where arr[j] is less than the current element arr[i] if (sum[i] < sum[j] && arr[i] > arr[j]) sum[i] = sum[j]; } // include arr[i] in MSIS sum[i] += arr[i]; } // find increasing subsequence with maximum sum int msis = INT_MIN; for (int x : sum) msis = max(msis, x); return msis; } // main function int main() { int arr[] = { 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int n = sizeof(arr)/sizeof(arr[0]); cout << "Maximum sum of increasing subsequence is " << MSIS(arr, n); return 0; } |

`Output:`

Maximum sum of increasing subsequence is 34

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(n).

#### How to print MSIS?

Above solutions only print the sum of MSIS but do not actually print MSIS itself. To print the MSIS, we actually have to store the maximum sum increasing subsequence in lookup table along with storing maximum sum.

For example, consider

arr = [ 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11]

The Maximum sum Increasing Subsequence MSIS[i] of subarray arr[0..i] that ends with arr[i] are –

MSIS[0] – 8

MSIS[1] – 4

MSIS[2] – 8 12

MSIS[3] – 2

MSIS[4] – 8 10

MSIS[5] – 4 6

**MSIS[6] – 8 12 14**

MSIS[7] – 1

MSIS[8] – 4 6 9

MSIS[9] – 4 5

MSIS[10] – 8 12 13

MSIS[11] – 2 3

MSIS[12] – 4 6 9 11

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <bits/stdc++.h> using namespace std; // Iterative function to print increasing subsequence with the maximum sum void printMSIS(int arr[], int n) { // MSIS[i] stores the increasing subsequence having maximum sum // that ends with arr[i] vector<int> MSIS[n]; MSIS[0].push_back(arr[0]); // sum[i] stores the maximum sum of the increasing subsequence // that ends with arr[i] int sum[n] = { 0 }; sum[0] = arr[0]; // start from second element in the array for (int i = 1; i < n; i++) { // do for each element in subarray arr[0..i-1] for (int j = 0; j < i; j++) { // find increasing subsequence with maximum sum that ends with // arr[j] where arr[j] is less than the current element arr[i] if (sum[i] < sum[j] && arr[i] > arr[j]) { MSIS[i] = MSIS[j]; // update increasing subsequence sum[i] = sum[j]; // update maximum sum } } // include current element in increasing subsequence MSIS[i].push_back(arr[i]); // add current element to maximum sum sum[i] += arr[i]; } // uncomment below lines to print contents of vector MSIS /* for (int i = 0; i < n; i++) { cout << "MSIS[" << i << "] - "; for (int j : MSIS[i]) cout << j << " "; cout << endl; } */ // j will contain index of MSIS int j = 0; for (int i = 1; i < n; i++) if (sum[i] > sum[j]) j = i; // print MSIS for (int i : MSIS[j]) cout << i << " "; } // main function int main() { int arr[] = { 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int n = sizeof(arr) / sizeof(arr[0]); printMSIS(arr, n); return 0; } |

`Output:`

8 12 14

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(n^{2}).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply