188. Maximum Sum Increasing Subsequence

Given an array arr[] of positive integers, find the maximum possible sum of a subsequence such that the elements of the subsequence are in strictly increasing order.

  • The subsequence does not need to be contiguous.
  • You must choose elements such that their order in the array is preserved and each chosen element is strictly greater than the previous one.

Example 1:

Input: arr = [1, 101, 2, 3, 100]

Output: 106

Explanation: The subsequence [1, 2, 3, 100] is strictly increasing and has the maximum sum = 106.

Example 2:

Input: arr = [4, 1, 2, 3]

Output: 6

Explanation: The maximum sum increasing subsequence is [1, 2, 3], sum = 6.

Now Your Turn!

Pick the correct output for the given input

Input: arr = [4, 1, 2, 4]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 1 <= arr.length <= 103
  • 1 <= arr[i] <= 105

Fun Facts

0
class Solution {
public:
int maxSumIncreasingSubsequence(vector<int>& arr, int n) {
// Your code goes here
}
};
Test Case

Input:

Arr
to save your code