# Maximum Sum Increasing Subsequence

Let's solve the Maximum Sum Increasing Subsequence problem using Dynamic Programming.

## Statement

Given an array of integers `nums`

, identify the increasing subsequence whose sum is the highest among all increasing subsequences. Return the sum.
Note that an increasing subsequence of an array is defined as a subsequence whose elements are sorted in strictly increasing order.

Let’s say we have an integer array [4, 1, 2, 6, 10, 1, 12], and we want to get the maximum sum increasing subsequence in this array. There are multiple increasing subsequences with different sums, [1, 2, 6, 10, 12], [2, 6, 10, 12], [6, 10, 12], [4, 6, 10, 12], and so on. The maximum sum increasing subsequence (MSIS), in this case, is [4, 6, 10, 12], with sum 32.

**Constraints:**

- $1 \leq$
`nums.length`

$\leq 5500$ - $-10^9 \leq$
`nums[i]`

$\leq 10^9$

## Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.