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)$.

Related

• Longest Common Subsequence