CJ

Explore

Tracks

My Courses

Edpresso

Refer a Friend

Create

Grokking Dynamic Programming Patterns for Coding Interviews

97% completed

Introduction

What is Dynamic Programming?

Pattern 1: 0/1 Knapsack

0/1 Knapsack

Equal Subset Sum Partition

Subset Sum

Minimum Subset Sum Difference

Count of Subset Sum

Target Sum

Pattern 2: Unbounded Knapsack

Unbounded Knapsack

Rod Cutting

Coin Change

Minimum Coin Change

Maximum Ribbon Cut

Pattern 3: Fibonacci Numbers

Fibonacci numbers

Staircase

Number factors

Minimum jumps to reach the end

Minimum jumps with fee

House thief

Pattern 4: Palindromic Subsequence

Longest Palindromic Subsequence

Longest Palindromic Substring

Count of Palindromic Substrings

Minimum Deletions in a String to make it a Palindrome

Palindromic Partitioning

Pattern 5: Longest Common Substring

Longest Common Substring

Longest Common Subsequence

Minimum Deletions & Insertions to Transform a String into another

Longest Increasing Subsequence

Maximum Sum Increasing Subsequence

Shortest Common Super-sequence

Minimum Deletions to Make a Sequence Sorted

Longest Repeating Subsequence

Subsequence Pattern Matching

Longest Bitonic Subsequence

Longest Alternating Subsequence

Edit Distance

Strings Interleaving

Appendix

Contact Us

Other courses

Mark Course as Completed

Maximum Sum Increasing Subsequence

We'll cover the following

Problem Statement

Basic Solution

Top-down Dynamic Programming with Memoization

Bottom-up Dynamic Programming

Problem Statement #

Given a number sequence, find the increasing subsequence with the highest sum. Write a method that returns the highest sum.

Example 1:

Input: {4,1,2,6,10,1,12}
Output: 32
Explanation: The increaseing sequence is {4,6,10,12}.
Please note the difference, as the LIS is {1,2,6,10,12} which has a sum of '31'.

Example 2:

Input: {-4,10,3,7,15}
Output: 25
Explanation: The increaseing sequences are {10, 15} and {3,7,15}.

Basic Solution #

The problem is quite similar to the Longest Increasing Subsequence. The only difference is that, instead of finding the increasing subsequence with the maximum length, we need to find an increasing sequence with the maximum sum.

A basic brute-force solution could be to try all the subsequences of the given array. We can process one number at a time, so we have two options at any
step:

If the current number is greater than the previous number that we included, we include that number in a running sum and make a recursive call for the remaining array.

We can skip the current number to make a recursive call for the remaining array.

The highest sum of any increasing subsequence would be the max value returned by the two recurse calls from the above two options.

Here is the code:

Java

Java

Java

JS

JS

Python3

Python3

C++

C++

class MSIS {

public int findMSIS(int[] nums) {
return findMSISRecursive(nums, 0, -1, 0);
}

private int findMSISRecursive(int[] nums, int currentIndex, int previousIndex, int sum) {
if(currentIndex == nums.length)
return sum;

// include nums[currentIndex] if it is larger than the last included number
int s1 = sum;
if(previousIndex == -1 || nums[currentIndex] > nums[previousIndex])
s1 = findMSISRecursive(nums, currentIndex+1, currentIndex, sum + nums[currentIndex]);

// excluding the number at currentIndex
int s2 = findMSISRecursive(nums, currentIndex+1, previousIndex, sum);

return Math.max(s1, s2);
}

public static void main(String[] args) {
MSIS msis = new MSIS();
int[] nums = {4,1,2,6,10,1,12};
System.out.println(msis.findMSIS(nums));
nums = new int[]{-4,10,3,7,15};
System.out.println(msis.findMSIS(nums));
}
}

RUN

SAVERESET

The time complexity of the above algorithm is exponential O(2n)O(2^n)O(2​n​​), where ‘n’ is the lengths of the input array. The space complexity is O(n)O(n)O(n) which is used to store the recursion stack.

Top-down Dynamic Programming with Memoization #

We can use memoization to overcome the overlapping subproblems.

The three changing values for our recursive function are the current index, the previous index, and the sum. An efficient way of storing the results of the subproblems could be a hash-table whose key would be a string (currentIndex + “|” + previousIndex + “|” + sum).

Here is the code:

Java

Java

Java

JS

JS

Python3

Python3

C++

C++

import java.util.HashMap;
import java.util.Map;

class MSIS {

public int findMSIS(int[] nums) {
Map<String, Integer> dp = new HashMap<>();
return findMSISRecursive(dp, nums, 0, -1, 0);
}

private int findMSISRecursive(Map<String, Integer> dp, int[] nums, int currentIndex, int previousIndex, int sum) {
if(currentIndex == nums.length)
return sum;

String subProblemKey = currentIndex + "-" + previousIndex + "-" + sum;
if(!dp.containsKey(subProblemKey)) {
// include nums[currentIndex] if it is larger than the last included number
int s1 = sum;
if(previousIndex == -1 || nums[currentIndex] > nums[previousIndex])
s1 = findMSISRecursive(dp, nums, currentIndex+1, currentIndex, sum + nums[currentIndex]);

// excluding the number at currentIndex
int s2 = findMSISRecursive(dp, nums, currentIndex+1, previousIndex, sum);
dp.put(subProblemKey, Math.max(s1, s2));
}

return dp.get(subProblemKey);
}

public static void main(String[] args) {
MSIS msis = new MSIS();
int[] nums = {4,1,2,6,10,1,12};
System.out.println(msis.findMSIS(nums));
nums = new int[]{-4,10,3,7,15};
System.out.println(msis.findMSIS(nums));
nums = new int[]{1,3,8,4,14,6,14,1,9,4,13,3,11,17,29};
System.out.println(msis.findMSIS(nums));
}
}

RUN

SAVERESET

Bottom-up Dynamic Programming #

The above algorithm tells us two things:

If the number at the current index is bigger than the number at the previous index, we include that number in the sum for an increasing sequence up to the current index.

But if there is a maximum sum increasing subsequence (MSIS), without including the number at the current index, we take that.

So we need to find all the increasing subsequences for a number at index i, from all the previous numbers (i.e. numbers till index i-1), to find MSIS.

If i represents the currentIndex and ‘j’ represents the previousIndex, our recursive formula would look like:

if num[i] > num[j] => dp[i] = dp[j] + num[i] if there is no bigger MSIS for 'i'

Let’s draw this visually for {-4,10,3,7,15}. Start with a subsequence of length ‘1’, as every number can represent an MSIS:

Every number is a LIS of length '1'

1 of 11

i:1, j:0 => Since num[i] > num[j] but dp[i] > dp[j]+ nums[i], therefore no update

2 of 11

i:2, j:0 => Since num[i] > num[j] but dp[i] > dp[j]+ nums[i], therefore no update

3 of 11

i:2, j:1 => Since num[i] < num[j], therefore no update

4 of 11

i:3, j:0 => Since num[i] > num[j] but dp[i] > dp[j]+ nums[i], therefore no update

5 of 11

i:3, j:1 => Since num[i] < num[j], therefore no update

6 of 11

i:3, j:2 => Since num[i] > num[j] and dp[i] < dp[j] + num[i], therefore dp[i] = dp[j] + num[i]

7 of 11

i:4, j:0 => Since num[i] > num[j] but dp[i] > dp[j]+ nums[i], therefore no update

8 of 11

i:4, j:1 => Since num[i] > num[j] and dp[i] < dp[j] + num[i], therefore dp[i] = dp[j] + num[i]

9 of 11

i:4, j:2 => Since num[i] > num[j] but dp[i] > dp[j]+ nums[i], therefore no update

10 of 11

i:4, j:3 => Since num[i] > num[j] but dp[i] == dp[j]+ nums[i], therefore no update

11 of 11

From the above visualization, we can clearly see that the maximum sum of any increasing subsequence is ‘25’ – as shown by dp[4].

Here is the code for our bottom-up dynamic programming approach:

Java

Java

Java

JS

JS

Python3

Python3

C++

C++

class MSIS {

public int findMSIS(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];

int maxSum = nums[0];
for (int i=1; i<nums.length; i++) {
dp[i] = nums[i];
for (int j=0; j<i; j++) {
if (nums[i] > nums[j] && dp[i] < dp[j] + nums[i])
dp[i] = dp[j] + nums[i];
}
maxSum = Math.max(maxSum, dp[i]);
}

return maxSum;
}

public static void main(String[] args) {
MSIS msis = new MSIS();
int[] nums = {4,1,2,6,10,1,12};
System.out.println(msis.findMSIS(nums));
nums = new int[]{-4,10,3,7,15};
System.out.println(msis.findMSIS(nums));
nums = new int[]{1,3,8,4,14,6,14,1,9,4,13,3,11,17,29};
System.out.println(msis.findMSIS(nums));
}
}

RUN

SAVERESET

The time complexity of the above algorithm is O(n2)O(n^2)O(n​2​​) and the space complexity is O(n)O(n)O(n).

Completed

←    Back
Longest Increasing Subsequence

Next    →
Shortest Common Super-sequence

Report an Issue

Ask a Question