Max Sum Increasing Subsequence

Tags

Max Sum Increasing Subsequence

Category

Dynamic Programming

Difficulty

Hard

Problem Statement

Given a non-empty array of integers, find the increasing subsequence with the maximum sum and return both the maximum sum and the subsequence itself. A subsequence is a set of elements that are in the same order as they appear in the array, but not necessarily contiguous. The subsequence must be strictly increasing.

Intuition

This is a variation of the Longest Increasing Subsequence (LIS) problem, but instead of maximizing length, we maximize the sum. For each element, we look at all previous elements that are smaller and choose the one whose subsequence sum, when extended by the current element, gives the largest total. We track both the maximum sum ending at each index and the predecessor indices to reconstruct the actual subsequence.

Approach

  1. Create an array sums where sums[i] is initialized to array[i] (each element is a subsequence of length 1 by itself).
  2. Create an array sequences to track predecessors, initialized to null.
  3. Track the index of the overall maximum sum.
  4. For each index i from 0 to n-1: a. For each index j from 0 to i-1:
    • If array[j] < array[i] and sums[j] + array[i] > sums[i]:
      • Update sums[i] = sums[j] + array[i].
      • Set sequences[i] = j. b. Update the overall maximum sum index if needed.
  5. Backtrack through sequences from the maximum sum index to reconstruct the subsequence.

Pseudocode

function maxSumIncreasingSubsequence(array):
    n = length(array)
    sums = copy of array
    sequences = array of n nulls
    maxSumIdx = 0

    for i from 0 to n - 1:
        for j from 0 to i - 1:
            if array[j] < array[i] and sums[j] + array[i] > sums[i]:
                sums[i] = sums[j] + array[i]
                sequences[i] = j
        if sums[i] > sums[maxSumIdx]:
            maxSumIdx = i

    // Reconstruct subsequence
    result = []
    idx = maxSumIdx
    while idx is not null:
        result.prepend(array[idx])
        idx = sequences[idx]

    return [sums[maxSumIdx], result]

Time & Space Complexity

  • Time: O(n^2), where n is the length of the array. For each element, we check all previous elements.
  • Space: O(n) for the sums and sequences arrays, plus the output subsequence.

Key Insights

  • This is essentially LIS with a different optimization criterion (sum instead of length).
  • Each element's initial sum is its own value, since a single element forms a valid subsequence.
  • Negative numbers can appear in the optimal subsequence if they lead to a larger sum when extended.
  • The predecessor tracking allows O(n) reconstruction of the actual subsequence.
  • Unlike the sum variant, the standard LIS problem can be solved in O(n log n), but the sum variant typically requires O(n^2).

Edge Cases

  • Single element array: return the element and a subsequence containing just it.
  • All elements are the same: each element alone is a subsequence; return the maximum single element.
  • Strictly decreasing array: the maximum sum subsequence is the single largest element.
  • Array with all negative numbers: the answer is the least negative (largest) single element.
  • Array with a mix of negative and positive numbers: negative numbers may still be excluded even if they are smaller, if they reduce the sum.

Linked mentions