Longest Increasing Subsequence (LIS)

You are given an array a[0 … n − 1] of numbers. A subsequence is what you get by deleting some elements (possibly none) and keeping the order of the remaining ones. For example, from [3, 1, 4, 1, 5, 9], the lists [3, 4, 5] and [1, 1, 5, 9] are both subsequences, but [4, 3] is not (the 4 comes after the 3 in the original).

A subsequence is strictly increasing if each element is larger than the one before it (no equal values allowed).

Find the length of the longest strictly increasing subsequence (LIS) of a.

Example. For a = [10, 9, 2, 5, 3, 7, 101, 18], one LIS is [2, 3, 7, 18] of length 4. (Another is [2, 5, 7, 18].)

Meaning of the state. Let lis(i) = length of the longest strictly increasing subsequence that ends exactly at index i — that is, the subsequence must use a[i] as its last element.

Idea in words. Take any strictly increasing subsequence ending at a[i]. Look at its previous element: it sits at some index j < i with a[j] < a[i]. The portion before a[i] is itself a strictly increasing subsequence ending at a[j], so its length is lis(j). Add 1 for a[i] and you have lis(j) + 1. To get lis(i), try every valid earlier index j and keep the best:

If no such j exists (e.g. a[i] is smaller than everything before it), the only subsequence ending at a[i] is [a[i]] itself, so lis(i) = 1.

Final answer. The LIS of the whole array can end anywhere, so:

Why this is correct. Any LIS must end at some index; we compute the best subsequence for each possible last index and take the overall maximum, so no LIS is missed.

Keep an array memo[0 … n − 1] with −1 for “not computed yet.” To compute lis(i), scan j = 0 … i − 1, recurse to get lis(j) (memoized), and track the best memo[j] + 1 subject to a[j] < a[i].

There are n states; each one does up to n − 1 comparisons, so the work is O(n²) time. Space is O(n) for the memo plus recursion depth at most n.

(There is a faster O(n log n) algorithm using patience sorting / binary search, but it is a separate technique — this page only covers the direct DP.)

Every index is its own length-1 increasing subsequence:

In the recurrence the max is taken over an empty set of valid j at the smallest indices (or whenever a[i] is a new minimum), so we treat that empty case as contributing 0 before adding 1 — which gives lis(i) = 1. In code we initialize the running best to 0 before the loop, and then return best + 1.

Take a = [10, 9, 2, 5, 3, 7, 101, 18] (indices 0 … 7). Compute lis(i) left to right.

• i = 0, a[0] = 10: no earlier indices. lis(0) = 1.
• i = 1, a[1] = 9: only a[0] = 10, not less than 9. lis(1) = 1.
• i = 2, a[2] = 2: nothing earlier is < 2. lis(2) = 1.
• i = 3, a[3] = 5: only a[2] = 2 < 5 qualifies; lis(2) + 1 = 2. So lis(3) = 2.
• i = 4, a[4] = 3: only a[2] = 2 < 3; lis(2) + 1 = 2. So lis(4) = 2.
• i = 5, a[5] = 7: candidates a[2]=2, a[3]=5, a[4]=3 all < 7. Best lis among them is lis(3) = 2 (or lis(4) = 2). So lis(5) = 2 + 1 = 3.
• i = 6, a[6] = 101: every earlier element is < 101. Best lis is lis(5) = 3. So lis(6) = 4.
• i = 7, a[7] = 18: candidates with a[j] < 18 are indices 2, 3, 4, 5 with lis values 1, 2, 2, 3. Best is 3 (from j = 5). So lis(7) = 4.

Final answer. max(1, 1, 1, 2, 2, 3, 4, 4) = 4, the length of an LIS such as [2, 3, 7, 18] or [2, 5, 7, 101].

Two small functions. LIS-END-AT(i) answers “how long is the best increasing subsequence that ends exactly at a[i]?” — it looks at every earlier smaller element, finds the best run it can extend, and adds 1 for a[i] itself. LIS then simply tries every possible ending index and keeps the maximum.

Time: O(n²) — each of the n states scans up to n earlier indices. Space: O(n) for the memo, plus recursion depth at most n.