Topics › Dynamic Programming › DP on LIS

Maximum Sum Increasing Subsequence

Medium TUF ID 698 SDE

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given an array arr of n positive integers, find the largest possible sum of a strictly increasing subsequence. A subsequence keeps the original order but may skip elements; “strictly increasing” means every chosen element is larger than the one chosen before it, so equal values cannot both be used.

Constraints in the usual version (GFG, “Maximum sum increasing subsequence”): 1 ≤ n ≤ 10^3, positive values. The last approach below also handles n = 10^5.

Example 1

arr = [1, 101, 2, 3, 100]
answer = 106        // 1 + 2 + 3 + 100

Example 2

arr = [4, 6, 1, 3, 8, 4, 6]
answer = 18         // 4 + 6 + 8

Example 3

arr = [1, 2, 3, 100, 4, 5, 6, 7]
answer = 106        // 1 + 2 + 3 + 100; the longest increasing subsequence 1..7 only sums to 28

Example 3 is the reason this is a separate problem from the Longest Increasing Subsequence: the longest chain and the heaviest chain can be completely different.

Approach 1: Recursion

Intuition. Walk through the array making one decision per element: skip it, or take it. Taking is allowed only if the element is larger than the last element taken, so the recursion needs to remember the index prev of the last taken element (-1 when nothing has been taken yet). The answer from index i onwards is the better of the two choices.

Algorithm.

1. solve(i, prev): if i == n, return 0.
2. skip = solve(i + 1, prev).
3. If prev == -1 or arr[i] > arr[prev]: take = arr[i] + solve(i + 1, i); otherwise take = 0.
4. Return max(skip, take); the answer is solve(0, -1).

static int recursion(int[] arr) {
    return solve(0, -1, arr);
}

/** Best sum obtainable from arr[i..] when the last chosen index is prev (-1 means nothing chosen yet). */
static int solve(int i, int prev, int[] arr) {
    if (i == arr.length) return 0;
    int skip = solve(i + 1, prev, arr);
    int take = 0;
    if (prev == -1 || arr[i] > arr[prev]) take = arr[i] + solve(i + 1, i, arr);
    return Math.max(skip, take);
}

Complexity. Time O(2^n): each element doubles the number of paths. Space O(n) for the recursion stack.

Approach 2: Memoization

Intuition. The result of solve(i, prev) depends only on the pair, and i ranges over n values while prev ranges over n + 1 values (including -1). So there are only O(n^2) distinct calls. Store each result in memo[i][prev + 1]; the + 1 shift lets prev = -1 use column 0. Since all values are positive, every real result is ≥ 0 and -1 can mark “not computed”.

static int memoization(int[] arr) {
    int n = arr.length;
    int[][] memo = new int[n][n + 1];
    for (int[] row : memo) Arrays.fill(row, -1);
    return solveMemo(0, -1, arr, memo);
}

static int solveMemo(int i, int prev, int[] arr, int[][] memo) {
    if (i == arr.length) return 0;
    if (memo[i][prev + 1] != -1) return memo[i][prev + 1];
    int skip = solveMemo(i + 1, prev, arr, memo);
    int take = 0;
    if (prev == -1 || arr[i] > arr[prev]) take = arr[i] + solveMemo(i + 1, i, arr, memo);
    return memo[i][prev + 1] = Math.max(skip, take);
}

Complexity. Time O(n^2), space O(n^2) for the table plus O(n) stack.

Approach 3: Tabulation, best sum ending at each index

Intuition. A cleaner state uses only one index. Let dp[i] be the largest sum of an increasing subsequence that ends exactly at index i. In such a subsequence, the element before arr[i] (if there is one) is some arr[j] with j < i and arr[j] < arr[i]. The part ending at j should itself be as heavy as possible: replacing it with a heavier increasing subsequence that also ends at arr[j] keeps the whole thing increasing. Hence

dp[i] = arr[i] + max(0, max of dp[j] over j < i with arr[j] < arr[i]),

and the answer is the largest dp[i]. This also cuts the memory from O(n^2) to O(n).

Algorithm.

1. For each i: start with dp[i] = arr[i] (the subsequence containing only arr[i]).
2. For every j < i with arr[j] < arr[i]: dp[i] = max(dp[i], dp[j] + arr[i]).
3. Track the maximum over all dp[i].

static int tabulation(int[] arr) {
    int n = arr.length, best = 0;
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        dp[i] = arr[i];                                    // the subsequence containing only arr[i]
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + arr[i]);
        }
        best = Math.max(best, dp[i]);
    }
    return best;
}

Dry run on Example 1:

Complexity. Time O(n^2) from the double loop, space O(n).

Approach 4: Optimal, Fenwick tree over values

Intuition. The inner loop answers one question: “what is the largest dp[j] among earlier positions whose value is smaller than arr[i]?” If we index the stored dp values by array value instead of by position, this becomes a prefix-maximum query over all values below arr[i], on a structure that receives one update per step as we move left to right. A Fenwick tree (binary indexed tree) supports both operations in O(log m):

• update(r, x): raise the entry at rank r to at least x;
• query(r): the maximum over ranks 1..r.

A Fenwick tree usually stores sums, but it also works for maximum as long as stored values only ever go up, which is true here. Values can be large, so we first compress them to ranks 1..m among the distinct values. Querying rank r - 1 instead of r excludes equal values, which keeps the subsequence strictly increasing.

Algorithm.

1. Sort the distinct values; the rank of x is its position in that list plus one.
2. For each x in array order: bestBefore = query(rank(x) - 1), cur = bestBefore + x, then update(rank(x), cur) and update the answer.

static int fenwick(int[] arr) {
    int[] sorted = Arrays.stream(arr).distinct().sorted().toArray();
    int[] tree = new int[sorted.length + 1];               // tree over ranks 1..m, storing prefix maxima of dp
    int best = 0;
    for (int x : arr) {
        int rank = Arrays.binarySearch(sorted, x) + 1;     // 1-based rank of x among distinct values
        int bestBefore = 0;
        for (int r = rank - 1; r > 0; r -= r & -r) bestBefore = Math.max(bestBefore, tree[r]);   // values strictly below x
        int cur = bestBefore + x;                          // dp for this position
        for (int r = rank; r < tree.length; r += r & -r) tree[r] = Math.max(tree[r], cur);
        best = Math.max(best, cur);
    }
    return best;
}

Dry run on Example 1. The distinct sorted values are [1, 2, 3, 100, 101], with ranks 1..5.

Note how 101 does not influence 100: it sits at rank 5, outside the query range 1..3.

Complexity. Time O(n log n): the sort, plus one binary search, one query and one update of O(log n) each per element. Space O(n). The Java file runs it on 10^5 elements.

Edge cases and pitfalls

• Equal values. [1, 1, 1] gives 1, not 3. Use < (strict) in the tabulation and query rank - 1 in the Fenwick tree.
• Decreasing arrays. [10, 5, 4, 3] gives 10, the single largest element.
• Empty array. All four methods return 0, the sum of the empty subsequence.
• Negative numbers are excluded by the problem. If they were allowed and the subsequence had to be non-empty, the overall answer would need to start from Integer.MIN_VALUE instead of 0, otherwise an all-negative array would wrongly report 0.
• Overflow. With n = 10^3 and values up to 10^5, sums stay below 10^8. For n = 10^5 with large values, switch to long.
• Fenwick for max only works because updates never decrease a stored value; it cannot undo an update.

Related problems

• Longest Increasing Subsequence uses the same dp[i] with +1 in place of +arr[i].
• Print Longest Increasing Subsequence adds parent pointers to rebuild the chosen elements; the same trick works here.
• Longest Bitonic Subsequence combines an increasing pass from the left with one from the right.
• 0 and 1 Knapsack follows the same take-or-skip recursion pattern.