☕ DSA Java Articles

Topics › Dynamic Programming › DP on LIS

Print Longest Increasing Subsequence

Medium TUF ID 851 A2Z

Java source ↗ Edit this article ↗

Problem

Given an integer array a, return the elements of a longest strictly increasing subsequence. Usually several subsequences have the maximum length, so the problem fixes which one to return: the index-wise lexicographically smallest one. Compare two candidates by the array indices they use; at the first position where they differ, the one using the earlier index wins.

Constraints: 1 ≤ n ≤ 1000 in the usual version; the Java file also returns an empty list for an empty array.

Example 1

a = [10, 9, 2, 5, 3, 7, 101, 18]
answer = [2, 5, 7, 101]

There are four LIS of length 4: 2,5,7,101, 2,5,7,18, 2,3,7,101, 2,3,7,18. Their index lists are (2,3,5,6), (2,3,5,7), (2,4,5,6), (2,4,5,7); the first is smallest.

Example 2

a = [5, 4, 3]
answer = [5]        // every single element is an LIS of length 1; index 0 is the earliest

Knowing the length is not enough here: we must reconstruct an actual subsequence. The standard tool is the parent pointer: while computing the DP, remember which earlier element each best answer came from, then walk the pointers back.

Approach 1: Brute force recursion

Intuition. Generalise the take-or-skip recursion for the LIS length so that it returns the best subsequence itself (as a list of indices). At index i with last taken index prev:

Because each sub-result is itself the smallest for its subproblem, gluing i in front keeps the result the smallest overall.

static List<Integer> bruteForce(int[] a) {
    List<Integer> res = new ArrayList<>();
    for (int i : best(0, -1, a)) res.add(a[i]);
    return res;
}

static List<Integer> best(int i, int prev, int[] a) {
    if (i == a.length) return new ArrayList<>();
    List<Integer> skip = best(i + 1, prev, a);
    if (prev != -1 && a[i] <= a[prev]) return skip;                 // a[i] cannot be taken
    List<Integer> take = best(i + 1, i, a);
    take.add(0, i);
    return take.size() >= skip.size() ? take : skip;               // on a tie, take puts the smaller index first
}

Complexity. Time O(2^n · n): every take-or-skip choice is explored and lists are copied. Space O(n) stack (plus the lists). Useful as a reference for testing only.

Approach 2: DP with parent pointers

Intuition. Use the “LIS ending at i” DP: dp[i] is the length of the longest increasing subsequence ending at index i. While computing dp[i] = 1 + max(dp[j]) over j < i with a[j] < a[i], also store parent[i] = j for the j that achieved the maximum. Initialise parent[i] = i to mean “this subsequence starts here”.

At the end, let last be an index with the maximum dp. Following parent from last until an index points to itself visits the subsequence backwards; reversing gives the answer.

Which LIS does this return? Two choices make it the index-wise smallest one:

  1. last is the first index with the maximum length (we update only on a strictly larger dp).
  2. parent[i] is the smallest j that achieves the maximum (the inner loop runs left to right and updates only on a strict improvement).

Why that is enough rests on one fact: if i < i' have the same dp value, then a[i] ≥ a[i']. (If a[i] < a[i'], appending a[i'] to the best subsequence ending at i would give dp[i'] ≥ dp[i] + 1.) Also, the element at position k of any LIS has dp exactly k; a larger value would let us lengthen the LIS. Now compare our answer s with the true smallest answer b, from the back. s_L ≤ b_L because s_L is the first index of maximum length. If s_{k+1} ≤ b_{k+1}, then a[b_k] < a[b_{k+1}] ≤ a[s_{k+1}] by the fact above, so b_k (if it lies before s_{k+1}) was a valid parent candidate and s_k ≤ b_k; otherwise s_k < s_{k+1} ≤ b_k anyway. So s is position-by-position no larger than b, and since b is the smallest, s = b.

Algorithm.

  1. For each i: dp[i] = 1, parent[i] = i; for each j < i with a[j] < a[i] and dp[j] + 1 > dp[i], set dp[i] = dp[j] + 1, parent[i] = j. Track last.
  2. Walk from last through parent until a self-loop, collecting values; reverse.
static List<Integer> dpWithParent(int[] a) {
    int n = a.length;
    List<Integer> res = new ArrayList<>();
    if (n == 0) return res;
    int[] dp = new int[n], parent = new int[n];
    int last = 0;                                                   // first index where the maximum length ends
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        parent[i] = i;                                              // i points to itself: start of a subsequence
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {                 // strict '>' keeps the smallest such j
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > dp[last]) last = i;
    }
    res.add(a[last]);
    while (parent[last] != last) {
        last = parent[last];
        res.add(a[last]);
    }
    Collections.reverse(res);
    return res;
}

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

i a[i] dp[i] parent[i]
0 10 1 0
1 9 1 1
2 2 1 2
3 5 2 2
4 3 2 2
5 7 3 3 (first index with dp 2 and a smaller value)
6 101 4 5
7 18 4 5

last = 6; walking back gives 6 → 5 → 3 → 2, so the answer is [2, 5, 7, 101].

Complexity. Time O(n^2), space O(n). This is the expected interview solution.

Approach 3: Optimal, binary search with levels

Intuition. The O(n log n) tails method computes dp[i] for free: when a[i] lands at position pos of the tails array, the longest increasing subsequence ending at i has length pos + 1. Group the indices by that length into levels, each kept in index order. By the fact proved above, values inside one level never increase from left to right.

Rebuild exactly the subsequence that Approach 2 finds:

static List<Integer> binarySearchLevels(int[] a) {
    int n = a.length;
    int[] tails = new int[n];                                       // tails[k] = smallest last value of an increasing subsequence of length k + 1
    List<List<Integer>> levels = new ArrayList<>();                 // levels.get(k) = indices with dp = k + 1, in index order
    int len = 0;
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = len;                                       // first k with tails[k] >= a[i]
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (tails[mid] < a[i]) lo = mid + 1; else hi = mid;
        }
        tails[lo] = a[i];
        if (lo == len) {
            len++;
            levels.add(new ArrayList<>());
        }
        levels.get(lo).add(i);                                      // dp[i] = lo + 1
    }
    List<Integer> res = new ArrayList<>();
    if (len == 0) return res;
    int cur = levels.get(len - 1).get(0);                           // first index with the maximum length
    res.add(a[cur]);
    for (int k = len - 2; k >= 0; k--) {
        List<Integer> level = levels.get(k);                        // values here never increase left to right
        int lo = 0, hi = level.size() - 1;                          // first position whose value is below a[cur]
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[level.get(mid)] < a[cur]) hi = mid; else lo = mid + 1;
        }
        cur = level.get(lo);
        res.add(a[cur]);
    }
    Collections.reverse(res);
    return res;
}

Complexity. Time O(n log n): one binary search per element while building, one per level while rebuilding. Space O(n).

Edge cases and pitfalls