Maximum Sum Increasing Subsequence

Problem Statement

Given an array of positive integers, find the maximum sum of a subsequence such that the elements in the subsequence are in strictly increasing order.

Example:

• Input: arr = [1, 101, 2, 3, 100, 4, 5]
• Output: 106 (subsequence [1, 2, 3, 100] has sum = 106)

Noob-Friendly Explanation

Imagine you're picking numbers from a list, and every number you pick must be bigger than the last one you picked. You want the picked numbers to add up to the biggest total possible. It's like cherry-picking increasing values from a sequence to get the fattest sum. For [1, 101, 2, 3, 100, 4, 5], picking 1 → 2 → 3 → 100 gives 106, which is the best you can do!

Approach 1: Brute Force (Recursion)

Intuition

For each element, decide to include or skip it. Include only if it's greater than the previous included element. Track the sum instead of the count.

Algorithm

1. For each element, if it's greater than the last included, try including it (add its value)
2. Also try skipping it
3. Return the maximum sum

public class Solution {
    public int msis(int[] arr, int n, int prev, int curr) {
        if (curr == n) return 0;

        // Skip current
        int skip = msis(arr, n, prev, curr + 1);

        // Include current if it's increasing
        int include = 0;
        if (prev == -1 || arr[curr] > arr[prev]) {
            include = arr[curr] + msis(arr, n, curr, curr + 1);
        }

        return Math.max(skip, include);
    }

    public int maxSumIS(int[] arr) {
        return msis(arr, arr.length, -1, 0);
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - Each element has 2 choices
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Optimal (Bottom-Up DP)

Intuition

Similar to LIS but instead of counting length, we track sum. dp[i] stores the maximum sum of an increasing subsequence ending at index i. For each element, check all previous elements — if they're smaller, see if including the current element gives a better sum.

Algorithm

1. Initialize dp[i] = arr[i] for all i (each element is a subsequence by itself)
2. For each i, check all j < i: if arr[j] < arr[i], update dp[i] = max(dp[i], dp[j] + arr[i])
3. Answer is the maximum value in the dp array

public class Solution {
    public int maxSumIS(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];

        // Each element is a subsequence of sum = itself
        for (int i = 0; i < n; i++) {
            dp[i] = arr[i];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + arr[i]);
                }
            }
        }

        // Find the maximum in dp
        int maxSum = dp[0];
        for (int i = 1; i < n; i++) {
            maxSum = Math.max(maxSum, dp[i]);
        }

        return maxSum;
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - Two nested loops
• Space Complexity: O(n) - 1D DP array