Maximum Sum Increasing Subsequence

The problem, simply

You get a list of numbers. Choose some of them, keeping their order, so that each chosen number is strictly bigger than the one chosen before it. This is an increasing subsequence.

Give back the biggest possible sum of such a choice. The longest climb is not always the heaviest one.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each position i, ask: "what is the best climb that ends here?" Try every smaller number before it as the step before.

1. end(i) starts as a[i], the climb with only this number.
2. For every j < i with a[j] < a[i], try end(j) + a[i].
3. The answer is the biggest end(i).

class Solution {
    public int maxSumIS(int[] a) {
        int best = 0;
        for (int i = 0; i < a.length; i++) {
            best = Math.max(best, end(a, i));
        }
        return best;
    }

    private int end(int[] a, int i) {             // best climb that finishes on a[i]
        int best = a[i];
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                best = Math.max(best, end(a, j) + a[i]);
            }
        }
        return best;
    }
}

How long it takes: the same end(j) is recomputed many times, which grows like O(2^n) on an increasing list. Extra room: the waiting calls, O(n).

Way 2: the clever way

Fill the notes from left to right in an array dp, so each one is computed once.

1. dp[i] = a[i] to start.
2. For each j < i with a[j] < a[i]: dp[i] = max(dp[i], dp[j] + a[i]).
3. The answer is the biggest value in dp.

Arrows show which earlier boxes each box can build on. Gray boxes are not smaller, so they cannot be the step before.

class Solution {
    public int maxSumIS(int[] a) {
        int n = a.length;
        int[] dp = new int[n];
        int best = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = a[i];                                 // climb with only a[i]
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i]) {                        // a[j] can be the step before
                    dp[i] = Math.max(dp[i], dp[j] + a[i]);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }
}

How long it takes: each number looks back at all earlier numbers, O(n^2). Extra room: the dp array, O(n).

Watch out for

• Use < for strictly increasing. Some versions allow equal numbers, then use <=.
• Start each box at a[i], not 0, so a number alone still counts.
• If numbers can be negative, start best at the smallest value, not 0, and decide whether an empty choice is allowed.

What interviewers ask next

• Print the chosen numbers. Keep from[i], the j that gave the best, and walk back from the biggest box.
• Can it be faster than O(n^2)? Yes. Squash the values to ranks and use a Fenwick tree (or segment tree) that answers "best dp among values smaller than mine" in O(log n). Total O(n log n).
• Longest increasing subsequence instead of heaviest? Same table, add 1 instead of a[i]. There is also a patience sorting trick for O(n log n).
• Biggest sum of a bitonic sequence (up then down)? Run this left to right and right to left, then combine at each peak.

Remember this

Grown-up words: the climb is an increasing subsequence, the note per hold is dp[i], looking back at smaller holds is the longest increasing subsequence recurrence, and recomputing end(j) is an overlapping subproblem.