Maximum Sum Increasing Subsequence Problem

Maximum Sum Increasing Subsequence Problem — ExecCode Medium DSA Practice

Solve the Maximum Sum Increasing Subsequence problem on ExecCode. Free online medium DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

You are given an integer array a. A subsequence does not have to be contiguous, but the chosen values must stay in their original order and be strictly increasing. Return the maximum sum of any strictly increasing subsequence. Use a 64-bit integer. You are given: a — the array Return the maximum increasing-subsequence sum as a 64-bit integer. Equal values are not strictly increasing, so they cannot both be chosen. Let dp[i] be the best increasing sum that ends at index i.

Examples

Input {'a': [1, 101, 2, 3, 100, 4, 5]}; Output 106. Input {'a': [10, 5, 4, 3]}; Output 10. Input {'a': [1, 2, 3, 4, 5]}; Output 15

Constraints

1 <= a.length <= 1000 1000000000 <= a[i] <= 1000000000 The answer fits in a signed 64-bit integer

Practice Maximum Sum Increasing Subsequence free on ExecCode. Browse DSA problems, topic map, and placement guides.