Maximum Sum Increasing Subsequence

Maximum Sum Increasing Subsequence

The maximum sum increasing subsequence (MSIS) is solved by extending each element with the best (highest-sum) increasing chain that can legally precede it — for every index i, look back at every earlier index j whose value is strictly smaller, take whichever gives the biggest running sum, and add nums[i] on top; the answer is the best running sum over all indices, not necessarily ending at the last element.

Recognize the pattern

• Phrase mentions an increasing (or non-decreasing) subsequence, but the objective is sum, count, or some other weight — not length. That weight rules out the plain patience-sorting trick used for LIS length.
• Each element's best answer depends only on elements before it with a smaller value — a classic "look back at all valid predecessors" DP over a sequence.
• Closely related family: Longest Increasing Subsequence (LIS), Longest Bitonic Subsequence, Box Stacking — all share the "dp[i] = best ending exactly at i" skeleton.

Brute force → optimal

Brute force: enumerate every subsequence (2^n subsets), filter increasing ones, sum, take max. Time O(2^n · n), space O(n) for recursion — infeasible past n≈20.

Optimal (DP): define dp[i] = max sum of an increasing subsequence that ends at index i (element i included). For each i, scan all j < i; if nums[j] < nums[i], index i could extend that chain, so dp[i] = nums[i] + max(dp[j]) over qualifying j (or just nums[i] alone if no j qualifies). The final answer is max(dp[0..n-1]), because the best chain can end anywhere.

Plain patience sorting (the O(n log n) LIS trick) does not transfer as-is, because it tracks the smallest possible tail per length, and length is no longer the quantity being compared. But the O(n²) loop is not a hard floor: replace the inner scan with a coordinate-compressed Fenwick tree (or segment tree) keyed by value, storing the best dp seen so far at each value. For each i, a prefix-max query over "all compressed values less than nums[i]" replaces the inner loop, and a point update inserts dp[i] — both O(log n). That gives O(n log n) overall. Most interview settings still expect the simpler O(n²) DP first, with the Fenwick-tree version as a follow-up optimization.

Complexity, derived

Time: the outer loop runs n times; for each i the inner loop scans up to i prior elements. Total comparisons = 0+1+2+…+(n-1) = n(n-1)/2 → O(n²) for the straightforward DP. With coordinate compression plus a Fenwick/segment tree doing prefix-max queries and point updates, this drops to O(n log n).

Space: O(n) for the straightforward DP; O(n) for the Fenwick tree plus the compressed-value map for the faster version. (Reconstructing the actual subsequence, not just the sum, needs one more O(n) parent-pointer array in either version.)

Traced example

Input: {4, 1, 2, 6, 10, 1, 12}

Answer = max(dp) = 32, reconstructed chain 4 → 6 → 10 → 12. Note the plain-LIS chain {1,2,6,10,12} sums to only 31 — MSIS correctly rejects it in favor of the higher-value chain.

Reference implementation

class Solution {
    public int findMaxSumIncreasingSubsequence(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            // No elements: there is no subsequence, so define the sum as 0.
            // Callers that need "no answer exists" instead should special-case n == 0.
            return 0;
        }
        int[] dp = new int[n];
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            dp[i] = nums[i];
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + nums[i]);
                }
            }
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}

func findMaxSumIncreasingSubsequence(nums []int) int {
    n := len(nums)
    if n == 0 {
        // No elements: there is no subsequence, so define the sum as 0.
        // Callers that need "no answer exists" instead should special-case n == 0.
        return 0
    }
    dp := make([]int, n)
    maxSum := math.MinInt32
    for i := 0; i < n; i++ {
        dp[i] = nums[i]
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] && dp[j]+nums[i] > dp[i] {
                dp[i] = dp[j] + nums[i]
            }
        }
        if dp[i] > maxSum {
            maxSum = dp[i]
        }
    }
    return maxSum
}

Pitfalls

• Empty input (n = 0). Without an explicit guard, the loop never runs and the function silently returns the sentinel (Integer.MIN_VALUE in Java, math.MinInt32 in Go) instead of a meaningful value — always special-case n == 0 before the loop.
• Returning dp[n-1] instead of max(dp). The best chain often ends in the middle (e.g. index 6 vs. a later smaller element) — always track a running max across all i.
• Using "non-decreasing" vs "strictly increasing" incorrectly. The comparison nums[j] < nums[i] must match the problem's definition; swapping to <= silently allows equal-value chains.
• Negative numbers. With input containing a negative element (e.g. {-4,-2,-7,-1,-3}, all-negative), initializing dp[i] = nums[i] (not 0) is essential — a single negative element can still be a legitimate best-so-far, and clamping to 0 would wrongly let an "empty chain" outscore every real one.
• Forgetting parent pointers when the problem asks for the actual subsequence, not just the sum.

When to use / when not — trade-offs

Use the straightforward O(n²) DP whenever the metric to optimize (sum, product, count) is not simply "length," and n is modest (≤ ~5000 is typical in interview constraints) — it is simpler to write and to explain, and the constant factors are small. If the metric were plain length (standard LIS), prefer the patience-sorting / binary-search LIS algorithm — O(n log n) — since it only needs to track minimal tails per length, a trick that breaks once the objective is a sum (a shorter chain can beat a longer one in total value). For the sum objective at large n (10⁴–10⁵+), don't settle for O(n²): coordinate-compress the values and maintain a Fenwick/segment tree that answers "max dp among elements with strictly smaller value" — this gives the same O(n log n) asymptotics as LIS, at the cost of more code and a less obvious proof of correctness. Reach for the O(n²) version by default and reach for the tree-augmented version only when n is large enough that O(n²) actually times out.

Takeaways

• MSIS is LIS's DP skeleton with the objective swapped from "length" to "sum" — same dp[i]-ends-at-i recurrence, different aggregation.
• The O(n log n) LIS trick does not transfer unmodified because it optimizes for smallest tail per length, not per sum — but MSIS still has its own O(n log n) solution via coordinate compression + a Fenwick/segment tree over dp values, so O(n²) is a practical default, not an asymptotic floor.
• Always answer with max(dp), never dp[last] — the optimal chain can terminate anywhere.
• Initialize dp[i] = nums[i] to correctly handle negative or isolated elements, and guard n = 0 explicitly rather than relying on the sentinel value falling through.

Recall question: Why can't the O(n log n) patience-sorting technique used for plain LIS be adapted directly to maximize sum instead of length — and what data structure lets MSIS still reach O(n log n) by a different route?

Pattern: 1-D DP over sequences, dp[i] = best value ending at i, aggregated via a backward scan over valid predecessors (compare Longest Increasing Subsequence, Longest Bitonic Subsequence, Box Stacking).