Dynamic Programming

Longest Increasing Subsequence (LIS)

This is a classic problem that we studied in CS341.

Problem Formulation

• Input: An array $A[1\dots n]$ of integers
• Output: A longest increasing subsequence of $A$ (or just its length) (does not need to be contiguous)
• Example: $A=[7,1,3,10,11,5,19]$ has answer $[1,3,10,11,19]$
• Remark: there are $2^n$ subsequences (including an empty one, which doesn’t count)

My own proof: We define the following subproblem: Find the length of longest increasing subsequence of $A[0\dots i]$ that includes $A[i]$. We store the value in $dp[i]$.

We have a base case initializing $dp[i]=1$.

Let $j$ be the second last element part of the LIS. For this to hold, $A[j]<A[i]$ with $j<i$, then en the LIS is given by $1$ + the LIS of $A[0\dots j]$ that includes $j$

• $dp[i]=1+dp[j]$

Since we don’t know $j$, we can iterate over all possibilities.

We then come up with the algorithm:

• https://leetcode.com/problems/longest-increasing-subsequence/submissions/1233315399/

int lengthOfLIS(vector<int>& nums) {
    int ans = 0;
    int dp[nums.size()];
    for (int i=0;i<nums.size();i++) {
        dp[i] = 1;
        for (int j=0;j<i;j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

This runs in $O(n^2)$.

Can we solve it in better than O(n^2)?

Yes, you can do it in $O(n\log n)$:

• Maintain tails (min possible ending value for each length).
• For strictly increasing LIS: use lower_bound(tails, x) (first >= x)
• For non-decreasing: use upper_bound(tails, x) (first > x)
• If you need “answer at each i”, record pos+1 as you update.

We keep tails sorted/monotonic, and every time, we just binary search and update only 1 of the values.

vector<int> tails;
for (int h : obstacles) {
    int pos = upper_bound(tails.begin(), tails.end(), h) - tails.begin(); // non-decreasing
    if (pos == (int)tails.size()) tails.push_back(h);
    else tails[pos] = h;
    ans.push_back(pos + 1);
}

Related

• Longest Common Subsequence