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.