Maximum Sum Increasing Subsequence
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
class GFG {
public static int maxSum(int[] arr) {
// dp[i] -> Max increasing subsequence sum upto i, including 'i'
int dp[] = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
dp[i] = arr[i];
for (int j = 0; j < i; j++)
if (arr[j] < arr[i])
dp[i] = Math.max(dp[j] + arr[i], dp[i]);
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++)
max = Math.max(max, dp[i]);
return max;
}
}
Last updated