Grokking Dynamic Programming Interview in Python/

...

/

Maximum Sum Increasing Subsequence

Maximum Sum Increasing Subsequence

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

We'll cover the following...

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≤1 \leq nums.length ≤995\leq 995
  • −104≤-10^4 \leq nums[i] ≤104\leq 10^4

Examples

No.

Input

Output

MSIS Elements

1

[4, 1, 2, 6, 10, 1, 12]

32

[4, 6, 10, 12]

2

[-4, 10, 3, 7, 15]

25

[10, 15]

3

[5, 5, 5, 5, 5, 5, 5]

5

[5]

Try it yourself

Implement your solution in the following playground.

Press + to interact
Python
usercode > main.py
def MSIS_length(nums):



  # Write your code here



  return -1
Maximum Sum Increasing Subsequence

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach

Let’s first list down all the ideas that are needed to find the solution to this problem:

  • Each element of the array is either a part of an increasing subsequence or it is not.
  • To be part of an increasing subsequence, the current element needs to be greater than the previous element included in the subsequence.
  • To find the maximum sum increasing subsequence, we need to move from left to right, exhaustively generating all increasing subsequences, while keeping track of the one with the greatest sum found so far.

Now, let’s consider how we might write a recursive solution to this problem. The first thing to figure out is the base case: we’re moving from the start of the array to the end and we need to consider all the elements. We may skip elements as we go along, but the only place we can safely stop this traversal is at the end of the array. So, the base case is precisely that: when ...

Access this course and 1400+ top-rated courses and projects.