Maximum Sum Increasing Subsequence | DP-14

Given an array of n positive integers. Write a program to find the sum of maximum sum subsequence of the given array such that the integers in the subsequence are sorted in increasing order. For example, if input is {1, 101, 2, 3, 100, 4, 5}, then output should be 106 (1 + 2 + 3 + 100), if the input array is {3, 4, 5, 10}, then output should be 22 (3 + 4 + 5 + 10) and if the input array is {10, 5, 4, 3}, then output should be 10

Solution
This problem is a variation of standard Longest Increasing Subsequence (LIS) problem. We need a slight change in the Dynamic Programming solution of LIS problem. All we need to change is to use sum as a criteria instead of length of increasing subsequence.

Following are the Dynamic Programming solution to the problem :

C++

 `/* Dynamic Programming implementation  ` `of Maximum Sum Increasing Subsequence  ` `(MSIS) problem */` `#include ` `using` `namespace` `std; ` ` `  `/* maxSumIS() returns the maximum  ` `sum of increasing subsequence  ` `in arr[] of size n */` `int` `maxSumIS(``int` `arr[], ``int` `n)  ` `{  ` `    ``int` `i, j, max = 0;  ` `    ``int` `msis[n];  ` ` `  `    ``/* Initialize msis values  ` `    ``for all indexes */` `    ``for` `( i = 0; i < n; i++ )  ` `        ``msis[i] = arr[i];  ` ` `  `    ``/* Compute maximum sum values  ` `    ``in bottom up manner */` `    ``for` `( i = 1; i < n; i++ )  ` `        ``for` `( j = 0; j < i; j++ )  ` `            ``if` `(arr[i] > arr[j] &&  ` `                ``msis[i] < msis[j] + arr[i])  ` `                ``msis[i] = msis[j] + arr[i];  ` ` `  `    ``/* Pick maximum of  ` `    ``all msis values */` `    ``for` `( i = 0; i < n; i++ )  ` `        ``if` `( max < msis[i] )  ` `            ``max = msis[i];  ` ` `  `    ``return` `max;  ` `}  ` ` `  `// Driver Code  ` `int` `main()  ` `{  ` `    ``int` `arr[] = {1, 101, 2, 3, 100, 4, 5};  ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);  ` `    ``cout << ``"Sum of maximum sum increasing "` `            ``"subsequence is "` `<< maxSumIS( arr, n ) << endl;  ` `    ``return` `0;  ` `}  ` ` `  `// This is code is contributed by rathbhupendra `

C

 `/* Dynamic Programming implementation  ` `of Maximum Sum Increasing Subsequence  ` `(MSIS) problem */` `#include ` ` `  `/* maxSumIS() returns the maximum  ` `   ``sum of increasing subsequence ` `   ``in arr[] of size n */` `int` `maxSumIS(``int` `arr[], ``int` `n) ` `{ ` `    ``int` `i, j, max = 0; ` `    ``int` `msis[n]; ` ` `  `    ``/* Initialize msis values ` `       ``for all indexes */` `    ``for` `( i = 0; i < n; i++ ) ` `        ``msis[i] = arr[i]; ` ` `  `    ``/* Compute maximum sum values  ` `       ``in bottom up manner */` `    ``for` `( i = 1; i < n; i++ ) ` `        ``for` `( j = 0; j < i; j++ ) ` `            ``if` `(arr[i] > arr[j] &&  ` `                ``msis[i] < msis[j] + arr[i]) ` `                ``msis[i] = msis[j] + arr[i]; ` ` `  `    ``/* Pick maximum of ` `       ``all msis values */` `    ``for` `( i = 0; i < n; i++ ) ` `        ``if` `( max < msis[i] ) ` `            ``max = msis[i]; ` ` `  `    ``return` `max; ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``int` `arr[] = {1, 101, 2, 3, 100, 4, 5}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]); ` `    ``printf``(``"Sum of maximum sum increasing "`  `            ````"subsequence is %d "````, ` `              ``maxSumIS( arr, n ) ); ` `    ``return` `0; ` `} `

Java

 `/* Dynamic Programming Java  ` `   ``implementation of Maximum Sum ` `   ``Increasing Subsequence (MSIS) ` `   ``problem */` `class` `GFG ` `{ ` `    ``/* maxSumIS() returns the  ` `    ``maximum sum of increasing ` `    ``subsequence in arr[] of size n */` `    ``static` `int` `maxSumIS(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``int` `i, j, max = ``0``; ` `        ``int` `msis[] = ``new` `int``[n]; ` ` `  `        ``/* Initialize msis values  ` `           ``for all indexes */` `        ``for` `(i = ``0``; i < n; i++) ` `            ``msis[i] = arr[i]; ` ` `  `        ``/* Compute maximum sum values ` `           ``in bottom up manner */` `        ``for` `(i = ``1``; i < n; i++) ` `            ``for` `(j = ``0``; j < i; j++) ` `                ``if` `(arr[i] > arr[j] && ` `                    ``msis[i] < msis[j] + arr[i]) ` `                    ``msis[i] = msis[j] + arr[i]; ` ` `  `        ``/* Pick maximum of all ` `           ``msis values */` `        ``for` `(i = ``0``; i < n; i++) ` `            ``if` `(max < msis[i]) ` `                ``max = msis[i]; ` ` `  `        ``return` `max; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `arr[] = ``new` `int``[]{``1``, ``101``, ``2``, ``3``, ``100``, ``4``, ``5``}; ` `        ``int` `n = arr.length; ` `        ``System.out.println(``"Sum of maximum sum "``+ ` `                            ``"increasing subsequence is "``+ ` `                              ``maxSumIS(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed  ` `// by Rajat Mishra  `

Python

 `# Dynamic Programming bsed Python  ` `# implementation of Maximum Sum  ` `# Increasing Subsequence (MSIS) ` `# problem ` ` `  `# maxSumIS() returns the maximum  ` `# sum of increasing subsequence  ` `# in arr[] of size n ` `def` `maxSumIS(arr, n): ` `    ``max` `=` `0` `    ``msis ``=` `[``0` `for` `x ``in` `range``(n)] ` ` `  `    ``# Initialize msis values ` `    ``# for all indexes ` `    ``for` `i ``in` `range``(n): ` `        ``msis[i] ``=` `arr[i] ` ` `  `    ``# Compute maximum sum  ` `    ``# values in bottom up manner ` `    ``for` `i ``in` `range``(``1``, n): ` `        ``for` `j ``in` `range``(i): ` `            ``if` `(arr[i] > arr[j] ``and` `                ``msis[i] < msis[j] ``+` `arr[i]): ` `                ``msis[i] ``=` `msis[j] ``+` `arr[i] ` ` `  `    ``# Pick maximum of ` `    ``# all msis values ` `    ``for` `i ``in` `range``(n): ` `        ``if` `max` `< msis[i]: ` `            ``max` `=` `msis[i] ` ` `  `    ``return` `max` ` `  `# Driver Code ` `arr ``=` `[``1``, ``101``, ``2``, ``3``, ``100``, ``4``, ``5``] ` `n ``=` `len``(arr) ` `print``(``"Sum of maximum sum increasing "` `+`  `                     ``"subsequence is "` `+` `                  ``str``(maxSumIS(arr, n))) ` ` `  `# This code is contributed  ` `# by Bhavya Jain `

C#

 `// Dynamic Programming C# implementation ` `// of Maximum Sum Increasing Subsequence ` `// (MSIS) problem  ` `using` `System; ` `class` `GFG { ` `     `  `    ``// maxSumIS() returns the  ` `    ``// maximum sum of increasing ` `    ``// subsequence in arr[] of size n  ` `    ``static` `int` `maxSumIS( ``int` `[]arr, ``int` `n ) ` `    ``{ ` `        ``int` `i, j, max = 0; ` `        ``int` `[]msis = ``new` `int``[n]; ` ` `  `        ``/* Initialize msis values ` `           ``for all indexes */` `        ``for` `( i = 0; i < n; i++ ) ` `            ``msis[i] = arr[i]; ` ` `  `        ``/* Compute maximum sum values ` `           ``in bottom up manner */` `        ``for` `( i = 1; i < n; i++ ) ` `            ``for` `( j = 0; j < i; j++ ) ` `                ``if` `( arr[i] > arr[j] && ` `                    ``msis[i] < msis[j] + arr[i]) ` `                    ``msis[i] = msis[j] + arr[i]; ` ` `  `        ``/* Pick maximum of all  ` `           ``msis values */` `        ``for` `( i = 0; i < n; i++ ) ` `            ``if` `( max < msis[i] ) ` `                ``max = msis[i]; ` ` `  `        ``return` `max; ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = ``new` `int``[]{1, 101, 2, 3, 100, 4, 5}; ` `        ``int` `n = arr.Length; ` `        ``Console.WriteLine(``"Sum of maximum sum increasing "``+ ` `                                        ``" subsequence is "``+ ` `        ``maxSumIS(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

PHP

 ` ``\$arr``[``\$j``] &&  ` `                ``\$msis``[``\$i``] < ``\$msis``[``\$j``] + ``\$arr``[``\$i``]) ` `                ``\$msis``[``\$i``] = ``\$msis``[``\$j``] + ``\$arr``[``\$i``]; ` ` `  `    ``// Pick maximum of all msis values ` `    ``for``(``\$i` `= 0;``\$i` `< ``\$n``; ``\$i``++ ) ` `        ``if` `(``\$max` `< ``\$msis``[``\$i``] ) ` `            ``\$max` `= ``\$msis``[``\$i``]; ` ` `  `    ``return` `\$max``; ` `} ` ` `  `    ``// Driver Code ` `    ``\$arr` `= ``array``(1, 101, 2, 3, 100, 4, 5); ` `    ``\$n` `= ``count``(``\$arr``); ` `    ``echo` `"Sum of maximum sum increasing subsequence is "`  `                                   ``.maxSumIS( ``\$arr``, ``\$n` `); ` `         `  `// This code is contributed by Sam007 ` `?> `

Output :

```Sum of maximum sum increasing subsequence is 106
```

Time Complexity: O(n^2)