Log inSign up
mediumGeeksforGeeksNot Started

Maximum Sum Increasing Subsequence

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of n positive integers arr, find the maximum sum of a subsequence such that the sequence is strictly increasing.

### Example 1 - Input: arr = [1, 101, 2, 3, 100, 4, 5] - Output: 106 - Explanation: The maximum sum increasing subsequence is [1, 2, 3, 100] which yields a sum of 1 + 2 + 3 + 100 = 106.

### Example 2 - Input: arr = [10, 5, 4, 3] - Output: 10 - Explanation: Maximum sum is achieved by a single-element subsequence [10].

Constraints:

  • 1 <= n <= 1000
  • 1 <= arr[i] <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Adapt standard LIS dynamic programming recurrence to optimize sum instead of count.
  • Understand the state formulation dp[i] = maximum sum ending at index i.
  • Perform array relaxation over all preceding elements.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Subsequence problem requiring strictly increasing order.
  • Objective is to maximize sum of elements, not count of elements.

Algorithmic Decision Tree:

  • dp[i] depends on max dp[j] among all j < i with arr[j] < arr[i].

Connected Patterns:

Longest Increasing SubsequenceLongest Bitonic SubsequenceNumber of Longest Increasing Subsequence

1. Recursive Inclusion / Exclusion

Intuition

Recursively check all subsequences, maintaining the last chosen element, and sum elements if strictly increasing.

Algorithm

  1. Define solve(idx, prevIdx).
  2. If idx == n, return 0.
  3. Exclude arr[idx]: solve(idx + 1, prevIdx).
  4. Include arr[idx]: if prevIdx == -1 || arr[idx] > arr[prevIdx], compute arr[idx] + solve(idx + 1, idx).
  5. Return max(exclude, include).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int idx, int prevIdx, const vector<int>& arr) {
9 if (idx == arr.size()) return 0;
10 int notTake = solve(idx + 1, prevIdx, arr);
11 int take = 0;
12 if (prevIdx == -1 || arr[idx] > arr[prevIdx]) {
13 take = arr[idx] + solve(idx + 1, idx, arr);
14 }
15 return max(notTake, take);
16 }
17public:
18 int maxSumIS(vector<int>& arr) {
19 return solve(0, -1, arr);
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> arr = {1, 101, 2, 3, 100, 4, 5};
26 cout << "Max Sum IS: " << sol.maxSumIS(arr) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) recursion stack

2. Memoized 2D DP

Intuition

Memoize solve(idx, prevIdx + 1) in an n x (n + 1) table.

Algorithm

  1. Allocate memo table memo[n][n+1] with -1.
  2. Map prevIdx = -1 to column 0 (prevIdx + 1).
  3. Store and return max(take, notTake).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int idx, int prevIdx, const vector<int>& arr, vector<vector<int>>& memo) {
9 if (idx == arr.size()) return 0;
10 if (memo[idx][prevIdx + 1] != -1) return memo[idx][prevIdx + 1];
11
12 int notTake = solve(idx + 1, prevIdx, arr, memo);
13 int take = 0;
14 if (prevIdx == -1 || arr[idx] > arr[prevIdx]) {
15 take = arr[idx] + solve(idx + 1, idx, arr, memo);
16 }
17 return memo[idx][prevIdx + 1] = max(notTake, take);
18 }
19public:
20 int maxSumIS(vector<int>& arr) {
21 int n = arr.size();
22 vector<vector<int>> memo(n, vector<int>(n + 1, -1));
23 return solve(0, -1, arr, memo);
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> arr = {1, 101, 2, 3, 100, 4, 5};
30 cout << "Max Sum IS: " << sol.maxSumIS(arr) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n^2) memo table + O(n) call stack

3. 1D Bottom-Up Tabulation (O(n^2) Time, O(n) Space)

Intuition

Define dp[i] as the maximum sum of an increasing subsequence ending at index i. Relax over all j < i with arr[j] < arr[i].

Algorithm

  1. Initialize array dp of size n with dp[i] = arr[i].
  2. Outer loop i from 1 to n - 1:
  3. Inner loop j from 0 to i - 1:
  4. If arr[j] < arr[i], dp[i] = max(dp[i], dp[j] + arr[i]).
  5. Return the maximum value in dp.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int maxSumIS(vector<int>& arr) {
10 int n = arr.size();
11 vector<int> dp = arr;
12 int maxSum = 0;
13
14 for (int i = 0; i < n; ++i) {
15 for (int j = 0; j < i; ++j) {
16 if (arr[j] < arr[i]) {
17 dp[i] = max(dp[i], dp[j] + arr[i]);
18 }
19 }
20 maxSum = max(maxSum, dp[i]);
21 }
22
23 return maxSum;
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> arr = {1, 101, 2, 3, 100, 4, 5};
30 cout << "Max Sum IS: " << sol.maxSumIS(arr) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Exclude/IncludeO(2^n)O(n)Exhaustive branching over all subsequences.Recomputes overlapping states
2.Memoized 2D DPO(n^2)O(n^2)Cache results indexed by (current_idx, prev_idx).Matrix allocation
3.1D Bottom-Up DPOptimalO(n^2)O(n)dp[i] is max sum ending at index i, relaxed over all j < i with arr[j] < arr[i].None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Initializing dp with 0 instead of arr[i]: A single element arr[i] alone has a sum equal to arr[i].

Pitfall 2:

Allowing equal elements: The sequence must be strictly increasing (arr[j] < arr[i]).

Crucial Edge Cases to Validate:

  • Strictly decreasing array (e.g., [10, 5, 4, 3]): Each single element forms its own subsequence; answer is the max element.
  • Strictly increasing array: The entire array is the subsequence; answer is sum of all elements.
  • Single element: Return arr[0].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight that unlike length-based LIS, patience sorting / binary search tails array cannot be directly used for maximum sum because a longer sequence might have a smaller sum.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does the recurrence for Maximum Sum Increasing Subsequence differ from standard Longest Increasing Subsequence (LIS)?

Back to DSA Sheet