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 the 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 a 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 <bits/stdc++.h> 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<stdio.h> /* 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\n", 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 |
Python3
# Dynamic Programming based 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
<?php // Dynamic Programming implementation // of Maximum Sum Increasing // Subsequence (MSIS) problem // maxSumIS() returns the maximum // sum of increasing subsequence // in arr[] of size n function maxSumIS($arr, $n) { $max = 0; $msis= array($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 $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 ?> |
Javascript
<script> // Dynamic Programming implementation // of Maximum Sum Increasing Subsequence // (MSIS) problem // maxSumIS() returns the maximum // sum of increasing subsequence // in arr[] of size n function maxSumIS(arr, n) { let i, j, max = 0; let msis = new Array(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 let arr = [ 1, 101, 2, 3, 100, 4, 5 ]; let n = arr.length; document.write("Sum of maximum sum increasing " + "subsequence is " + maxSumIS(arr, n)); // This code is contributed by rishavmahato348 </script> |
Output
Sum of maximum sum increasing subsequence is 106
Time Complexity: O(n^2)
Space Complexity O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
