Longest Increasing Subsequence

The problem, simply

You get a row of numbers. Choose some of them, keeping their order, so that each chosen number is strictly bigger than the one before it. You may skip as many as you like. How many can you choose at most?

The chosen numbers are an increasing subsequence. Give back the length of the longest one.

A story to remember it

Picture it

Examples

Way 1: the simple way

The plain recursion tries "take or skip" for every number, which is O(2^n). Most of those calls repeat, so store a smaller answer instead: dp[i] is the longest chain that ends exactly at arr[i].

1. Every number alone is a chain, so dp[i] starts at 1.
2. For each i, look back at every j < i. If arr[j] < arr[i], the chain ending at j can be extended by arr[i]: dp[i] = max(dp[i], dp[j] + 1).
3. The answer is the biggest dp[i].

class Solution {
    public int lengthOfLIS(int[] arr) {
        int n = arr.length, best = 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;                                   // the number alone
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);  // extend the chain at j
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }
}

How long it takes: every number looks back at all the numbers before it, O(n^2). Extra room: the dp array, O(n). This version is easy to change for "print the chain" or "count the chains", so learn it too.

Way 2: the clever way

Keep the pile tops from the story in an array tails. tails[k] is the smallest number that can end an increasing chain of length k + 1. The tops always go up from left to right, so you can binary search them.

1. For each number x, find the first slot in tails whose value is x or more.
2. If there is no such slot, x is bigger than every top: add it at the end. The longest chain grew by one.
3. Otherwise put x in that slot. A chain of that length can now end with a smaller number.
4. The answer is the size of tails.

class Solution {
    public int lengthOfLIS(int[] arr) {
        int[] tails = new int[arr.length];
        int size = 0;
        for (int x : arr) {
            int lo = 0, hi = size;              // search in tails[0..size)
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (tails[mid] < x) lo = mid + 1;
                else hi = mid;
            }
            tails[lo] = x;                      // replace, or add at the end
            if (lo == size) size++;
        }
        return size;
    }
}

How long it takes: one binary search per number, O(n log n). Extra room: the tails array, O(n).

Watch out for

• Strictly increasing needs "first slot that is >= x" (lower bound). If equal numbers are allowed in the chain (non-decreasing), search for the first slot that is > x (upper bound) instead.
• In Way 1 the answer is the biggest dp[i], not dp[n - 1]. The best chain does not have to end at the last number.
• Empty input: both ways return 0.

What interviewers ask next

• Print one longest chain: in Way 1, keep parent[i] = the j that gave the best dp[i], then walk back from the best end. In Way 2, store the index in each slot and a parent link for each number.
• Count how many longest chains there are: Way 1 with a second array count[i], adding counts when dp[j] + 1 ties the best.
• Russian doll envelopes: sort by width going up and by height going down for equal widths, then run Way 2 on the heights.
• Fewest numbers to delete so the row is increasing: n - LIS.
• Longest common subsequence of two orderings of the same distinct numbers: relabel one by positions in the other, then LIS solves it in O(n log n).

Remember this

Grown-up words: the chain is the longest increasing subsequence (LIS), the card piles are patience sorting, tails is the array of smallest tail values, the slot search is a lower bound binary search, and dp[i] in Way 1 is the "ends here" DP state.