☕ DSA Java Articles

Topics › Dynamic Programming › DP on LIS

Longest Increasing Subsequence

Medium TUF ID 636 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given an integer array a, return the length of its longest strictly increasing subsequence (LIS). A subsequence keeps the original order but may skip elements; it does not have to be contiguous.

Constraints: 1 ≤ n ≤ 2500 on LeetCode (the O(n log n) method handles 10^5 and more), values fit in a 32-bit int. The Java file also returns 0 for an empty array.

Example 1

a = [10, 9, 2, 5, 3, 7, 101, 18]
answer = 4          // for example 2, 3, 7, 101 or 2, 5, 7, 18

Example 2

a = [7, 7, 7, 7]
answer = 1          // strictly increasing: equal values cannot follow each other

LIS is the head of a whole family (“DP on LIS”): printing the sequence, divisible subsets, string chains, bitonic sequences and counting LIS all reuse the formulations below.

Approach 1: Recursion

Intuition. Scan the array and decide for each element: take it or skip it. Whether we may take a[i] depends on the last element we took, so the state is (i, prev), where prev is the index of the last taken element (-1 if none).

f(i, prev) = length of the LIS of a[i..] whose elements all exceed a[prev]:

The answer is f(0, -1). Storing the index rather than the value is what makes the state small enough to memoize later: prev has only n + 1 possible values.

static int recursive(int[] a) {
    return solve(0, -1, a);
}

static int solve(int i, int prev, int[] a) {
    if (i == a.length) return 0;
    int best = solve(i + 1, prev, a);                               // skip a[i]
    if (prev == -1 || a[i] > a[prev]) {
        best = Math.max(best, 1 + solve(i + 1, i, a));              // take a[i]
    }
    return best;
}

Complexity. Time O(2^n): every element is taken or skipped. Space O(n) stack.

Approach 2: Memoization

Intuition. There are n × (n + 1) states. Java arrays cannot be indexed by -1, so store f(i, prev) in column prev + 1 (the coordinate shift). Lengths are never negative, so -1 marks “not computed”.

static int memoization(int[] a) {
    int n = a.length;
    int[][] dp = new int[n][n + 1];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(0, -1, a, dp);
}

static int memo(int i, int prev, int[] a, int[][] dp) {
    if (i == a.length) return 0;
    if (dp[i][prev + 1] != -1) return dp[i][prev + 1];
    int best = memo(i + 1, prev, a, dp);
    if (prev == -1 || a[i] > a[prev]) best = Math.max(best, 1 + memo(i + 1, i, a, dp));
    return dp[i][prev + 1] = best;
}

Complexity. Time O(n^2): n^2 states, O(1) each. Space O(n^2) for the table plus O(n) stack.

Approach 3: Tabulation

Intuition. f(i, prev) reads f(i + 1, *), so fill rows from i = n - 1 down to 0. In each row, only prev < i is meaningful (the previous element comes before i), so prev runs from i - 1 down to -1. Row n is the zero base case. Keep the + 1 shift on every column index, including dp[i + 1][i + 1], which is f(i + 1, i).

static int tabulation(int[] a) {
    int n = a.length;
    int[][] dp = new int[n + 1][n + 1];                             // dp[n][*] = 0
    for (int i = n - 1; i >= 0; i--) {
        for (int prev = i - 1; prev >= -1; prev--) {
            int best = dp[i + 1][prev + 1];
            if (prev == -1 || a[i] > a[prev]) best = Math.max(best, 1 + dp[i + 1][i + 1]);
            dp[i][prev + 1] = best;
        }
    }
    return dp[0][0];
}

Complexity. Time O(n^2), space O(n^2).

Approach 4: Space optimised

Intuition. Row i reads only row i + 1. Keep two arrays, next and cur, and swap them after each row.

static int spaceOptimized(int[] a) {
    int n = a.length;
    int[] next = new int[n + 1], cur = new int[n + 1];
    for (int i = n - 1; i >= 0; i--) {
        for (int prev = i - 1; prev >= -1; prev--) {
            int best = next[prev + 1];
            if (prev == -1 || a[i] > a[prev]) best = Math.max(best, 1 + next[i + 1]);
            cur[prev + 1] = best;
        }
        int[] t = next; next = cur; cur = t;
    }
    return next[0];
}

Complexity. Time O(n^2), space O(n).

Approach 5: LIS ending at each index

Intuition. A different, more direct state: let dp[i] be the length of the longest increasing subsequence that ends at index i. Such a subsequence is either a[i] alone, or some increasing subsequence ending at an earlier j with a[j] < a[i], extended by a[i]. So dp[i] = 1 + max(dp[j]) over valid j, and the answer is the maximum dp[i], because the LIS has to end somewhere.

This version is shorter, uses O(n) memory, and is the one to extend when you need to print the subsequence (store which j gave the maximum) or count how many LIS there are.

static int endingAt(int[] a) {
    int n = a.length, best = 0;
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;                                                  // a[i] alone
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + 1);    // extend a subsequence ending at j
        }
        best = Math.max(best, dp[i]);
    }
    return best;
}

Dry run on a = [10, 9, 2, 5, 3, 7, 101, 18]:

i a[i] earlier smaller values dp[i]
0 10 none 1
1 9 none 1
2 2 none 1
3 5 2 (dp 1) 2
4 3 2 (dp 1) 2
5 7 2, 5, 3 (best dp 2) 3
6 101 all earlier (best dp 3) 4
7 18 10, 9, 2, 5, 3, 7 (best dp 3) 4

The maximum is 4.

Complexity. Time O(n^2), space O(n).

Approach 6: Optimal, binary search on tails

Intuition. Maintain tails[k] = the smallest possible last value of an increasing subsequence of length k + 1 seen so far. A smaller tail is always better, since it leaves more room to extend. The tails array is strictly increasing, so for each new x we binary search for the first tail ≥ x:

The length of tails is the LIS length. The array itself is generally not an actual subsequence; only its length is meaningful. On Example 1, tails evolves [10] → [9] → [2] → [2, 5] → [2, 3] → [2, 3, 7] → [2, 3, 7, 101] → [2, 3, 7, 18].

The full argument for why this works, with variants, is in Longest Increasing Subsequence - (DP-43).

static int binarySearch(int[] a) {
    int[] tails = new int[a.length];
    int len = 0;
    for (int x : a) {
        int lo = 0, hi = len;                                       // first k with tails[k] >= x
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (tails[mid] < x) lo = mid + 1; else hi = mid;
        }
        tails[lo] = x;
        if (lo == len) len++;
    }
    return len;
}

Complexity. Time O(n log n): one binary search per element. Space O(n).

Edge cases and pitfalls