Longest Increasing Subsequence

Given an array of integers, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements.

LeetCode: 300. Longest Increasing Subsequence

Example

Text

[10, 9, 2, 5, 3, 7, 101, 18]  ->  4   (for example 2, 3, 7, 18)
[0, 1, 0, 3, 2, 3]            ->  4   (0, 1, 2, 3)
[7, 7, 7, 7]                  ->  1

Brute force: include or skip each element

Walk the array and, at each element, either skip it or take it (if it's larger than the last element taken). last is an Integer (a boxed int that can be null); null means nothing has been taken yet.

Java

public class Main {
    static int lisFrom(int[] nums, int i, Integer last) {
        if (i == nums.length) return 0;
        int skip = lisFrom(nums, i + 1, last);
        int take = 0;
        if (last == null || nums[i] > last) {
            take = 1 + lisFrom(nums, i + 1, nums[i]);
        }
        return Math.max(skip, take);
    }

    static int lis(int[] nums) {
        return lisFrom(nums, 0, null);
    }

    public static void main(String[] args) {
        System.out.println(lis(new int[]{10, 9, 2, 5, 3, 7, 101, 18}) + " " + lis(new int[]{0, 1, 0, 3, 2, 3}) + " " + lis(new int[]{7, 7, 7, 7}));
    }
}

Output

4 4 1

Time: O(2ⁿ). Space: O(n) for the recursion.

Better: DP over ending positions

Let len[i] be the length of the longest increasing subsequence that ends at index i. It extends the best subsequence ending at some earlier, smaller element:

Text

len[i] = 1 + max(len[j]) over j < i with nums[j] < nums[i]    (or 1 if there is none)

Java

import java.util.Arrays;

public class Main {
    static int lis(int[] nums) {
        int[] len = new int[nums.length];
        Arrays.fill(len, 1);
        int best = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) len[i] = Math.max(len[i], len[j] + 1);
            }
            best = Math.max(best, len[i]);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(lis(new int[]{10, 9, 2, 5, 3, 7, 101, 18}) + " " + lis(new int[]{0, 1, 0, 3, 2, 3}) + " " + lis(new int[]{7, 7, 7, 7}));
    }
}

Output

4 4 1

Time: O(n²). Space: O(n).

Optimal: smallest tails with binary search

Keep tails, where tails[k] is the smallest possible last element of an increasing subsequence of length k + 1 seen so far. A smaller tail is always better, because more future values can extend it. tails is always sorted, so for each new value x:

if x is larger than every tail, it extends the longest subsequence: push it;
otherwise, it becomes the new, smaller tail for the first length whose tail is >= x. Replace that tail.

x	10	9	2	5	3	7	101	18
tails	10	9	2	2 5	2 3	2 3 7	2 3 7 101	2 3 7 18

The answer is the length of tails. tails itself isn't necessarily a real subsequence, only its length is meaningful.

Arrays.binarySearch is not used here: with duplicate values it may return any matching index, and it reports a miss as a negative number. The code uses a small lowerBound that returns the first index whose tail is >= x.

Java

public class Main {
    // first index in tails[0..size) whose value is >= x, or size if none
    static int lowerBound(int[] tails, int size, int x) {
        int lo = 0, hi = size;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    static int lis(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int k = lowerBound(tails, size, x);
            tails[k] = x;
            if (k == size) size++;
        }
        return size;
    }

    public static void main(String[] args) {
        System.out.println(lis(new int[]{10, 9, 2, 5, 3, 7, 101, 18}) + " " + lis(new int[]{0, 1, 0, 3, 2, 3}) + " " + lis(new int[]{7, 7, 7, 7}));
        System.out.println(lis(new int[]{}));
    }
}

Output

4 4 1
0

Time: O(n log n). Space: O(n).

Edge cases

Empty array: 0.
Equal values: don't count as increasing. For a non-decreasing subsequence, search with t <= x instead.
Recovering the subsequence: store, for each element, the index of its predecessor (the tail before it when it was placed), and walk back from the last tail.