Maximum Sum Increasing Subsequence

Practice Link

Given an array of positive integers arr. Find the maximum sum subsequence of the given array such that the integers in the subsequence are sorted in strictly increasing order i.e. a strictly increasing subsequence.

DP Approach#

msis[i] = maximum sum of an increasing subsequence ending at index i. Initialize each msis[i] = arr[i] (the element alone). For each i, scan all j < i: if arr[j] < arr[i], the element at i can extend the subsequence ending at j, so msis[i] = max(msis[i], arr[i] + msis[j]). The answer is the maximum over all msis[i]. This O(n^2) approach mirrors the LIS DP but sums values instead of counting steps.

class Solution {
  public:
    int maxSumIS(vector<int>& arr) {
        int n = arr.size();
        vector<int> msis(n);
        for(int i=0;i<n;i++)
        {
            msis[i] = arr[i];
            for(int j=0;j<i;j++)
            {
                if(arr[j] < arr[i])
                    msis[i] = max(msis[i], arr[i] + msis[j]);
            }
        }
        return *max_element(msis.begin(), msis.end());
    }
};

Time Complexity: O(n*n)

Space Compelexity: O(n)

Binary Search Approach#

Maintain a tail array where tail[i] holds the minimum tail value for an increasing subsequence of length i+1. For each new element, binary search for the first tail value >= arr[i] and replace it (or extend if it's larger than all tails). This keeps the tail array sorted and finds the insertion point in O(log n), reducing overall time from O(n^2) to O(n log n). Note: this variant tracks LIS length; adapting it to track sums requires additional bookkeeping.

class Solution {
public:

    int ceilIdx(vector<int> &tail, int l, int r, int x)
    {
        while(l < r)
        {
            int m = (l+r)/2;
            if(tail[m] >= x)
                r = m;
            else
                l = m+1;
        }
        return r;
    }

    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> tail(n);
        tail[0]=nums[0];
        int len = 1;

        for(int i=1;i<n;i++)
        {
            if(tail[len-1] < nums[i]){
                tail[len++] = nums[i];
            }
            else{
                int c = ceilIdx(tail, 0, len-1, nums[i]);
                tail[c] = nums[i];
            }
        }
        return len;
    }
};

Time Complexity: O(n*log n)

Space Complexity: O(n)