Dynamic Programming | Set 14 (Maximum Sum Increasing Subsequence) | GeeksforGeeks
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 intgers in the subsequence are sorted in increasing order.
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.
http://www.geeksforgeeks.org/printing-maximum-sum-increasing-subsequence/
Read full article from Dynamic Programming | Set 14 (Maximum Sum Increasing Subsequence) | GeeksforGeeks
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 intgers in the subsequence are sorted in increasing order.
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.
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; }http://www.geeksforgeeks.org/printing-maximum-sum-increasing-subsequence/
The Maximum Sum Increasing Subsequence problem is to find the maximum sum subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
-- change the int msis[] to an object array, the object contains the max sum that ends at i, and it's parent.
