Algorithm

Longest Increasing Subsequence

Dynamic Programming Pattern

Longest Increasing Subsequence

You are given an integer array nums. A subsequence is obtained by deleting zero or more elements without changing the order of the ones that remain. Return the length of the longest subsequence whose elements are in strictly increasing order. Equal neighbouring values do not count as increasing. Return the length only, not the subsequence itself.

CONSTRAINTS
  • 1 ≤ nums.length ≤ 2500
  • -10⁴ ≤ nums[i] ≤ 10⁴
  • The subsequence must be strictly increasing
  • Elements need not be adjacent, but must keep their original order
EXAMPLE 1
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
The subsequence 2, 5, 7, 101 increases at every step and has length 4. The choice 2, 3, 7, 18 also works and has the same length, and no length-5 increasing subsequence exists.
EXAMPLE 2
Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
The elements at indices 0, 1, 4 and 5 read 0, 1, 2, 3, which increases at every step. The repeated 0 at index 2 cannot be used alongside the 0 at index 0, since the sequence must increase strictly.
EXAMPLE 3
Input: nums = [7, 7, 7, 7, 7]
Output: 1
The sequence must increase strictly, and equal values do not increase, so no two elements can be taken together.
EXAMPLE 4
Input: nums = [5, 4, 3, 2, 1]
Output: 1
The array decreases everywhere, so the longest increasing subsequence is a single element.
EXAMPLE 5
Input: nums = [1, 2, 3, 4]
Output: 4
The whole array is already strictly increasing, and deleting nothing is a legal way to form a subsequence.
Must the subsequence be contiguous?
No — elements may be skipped as long as the remaining ones keep their original order. The contiguous version is a much easier problem, solvable with a single running counter that resets on every non-increase, so it is worth confirming which is meant.
Is 'increasing' strict, or does it allow equal values?
Strict here, so [7, 7] has an answer of 1. The non-decreasing variant changes only the comparison — a less-than becomes a less-than-or-equal in the quadratic version, and a left binary search becomes a right one in the fast version.
Do I need to return the subsequence itself?
Only its length. If the subsequence were required, the quadratic table is the easier base to work from, since you can store which earlier index each value extended and walk those links backwards from the best ending position.
Can the array contain negative numbers or duplicates?
Both are allowed. Negatives change nothing, since only comparisons matter. Duplicates matter a great deal under the strict rule, because two equal values can never appear together in the answer.
Is an O(N log N) solution expected?
At these bounds the quadratic version passes comfortably, so it is fine to write it first and then offer the faster one. If the length limit were raised to a hundred thousand or more, the faster method would become mandatory.
The definition, and one trap inside it

A subsequence keeps the original order but allows gaps. In [10, 9, 2, 5, 3, 7, 101, 18], the elements 2, 5, 7, 101 appear in that order — not next to each other, but never out of order — so [2, 5, 7, 101] is an increasing subsequence of length 4.

Strictly increasing means each element must be larger than the one before, so [7, 7, 7] has a longest increasing subsequence of length 1, not 3. That word is worth confirming out loud with an interviewer, because the non-strict version needs a different comparison in exactly one place and is otherwise identical.

Brute force is to generate all 2ⁿ subsequences and check each. For 2500 elements that number has 750 digits, so we need real structure.

The state that does not work, and the one that does

The first instinct is to define f(i) as "the length of the longest increasing subsequence within the first i elements". It sounds right and it is useless. Suppose f(5) = 3 — you know a length-3 subsequence exists somewhere in that prefix, but you have no idea what its last value is, and that is precisely what you need in order to decide whether nums[5] can be appended to it.

Two prefixes with the same best length can end on very different values, and those futures differ. So that state is no good — a state must decide what can happen next, and this one does not.

Key Insightfix it by making the state pin down the ending. Define f(i) as the length of the longest increasing subsequence that ends exactly at index i, using nums[i] as its final element. Now the ending value is known — it is nums[i] — and everything you need to extend is available.

The price of this definition is that f(i) is no longer the answer for the prefix; it is a local fact. The overall answer becomes the maximum of f(i) over all i, because every increasing subsequence ends somewhere, and whichever index that is will have recorded it.

The recurrence

What can come before nums[i] in a subsequence ending at i? Any earlier element that is strictly smaller. If we choose j < i with nums[j] < nums[i], then the best we can do is the best subsequence ending at j, plus this one element:

f(i) = 1 + max( f(j) for all j < i with nums[j] < nums[i] )

and if no such j exists, f(i) = 1 — the element standing alone.

python
def length_of_lis(nums):
    n = len(nums)
    dp = [1] * n                       # every element is a subsequence of length 1
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Count the cost: index i scans i earlier elements, so the total is about N²/2 — around three million operations at the maximum size, which is comfortably fast enough. This version is worth being able to write instantly, because it generalises to almost every variant.

Note the loops read only smaller indices, so the natural left-to-right order is already correct, and the base case dp[i] = 1 is folded into the initialisation.

Worked Example:nums = [10, 9, 2, 5, 3, 7, 101, 18]
- 10: nothing before it. dp = 1.
- 9: 10 is not smaller. dp = 1.
- 2: nothing smaller before it. dp = 1.
- 5: 2 is smaller, dp[2] = 1, so dp = 2. (the subsequence 2, 5)
- 3: 2 is smaller, dp = 2. (2, 3) — note 5 does not qualify, being larger.
- 7: 2, 5 and 3 are all smaller; the best of their dp values is 2, so dp = 3. (2, 5, 7 or 2, 3, 7)
- 101: everything before is smaller; the best dp so far is 3, so dp = 4.
- 18: 10, 9, 2, 5, 3, 7 are smaller; best dp among them is 3 (from 7), so dp = 4.

dp = [1, 1, 1, 2, 2, 3, 4, 4], and the answer is max(dp) = 4.

Look at where the maximum lives: at indices 6 and 7, not at the end. This is exactly why the answer is a maximum over the table rather than its last entry.

The faster method, and why it is correct

There is an O(N log N) solution, and it is worth learning properly rather than memorising, because the reasoning is beautiful and the code is four lines.

Keep an array tails, where tails[k] holds the smallest possible value that any increasing subsequence of length k+1 could end with, considering everything processed so far.

Why do we want the smallest ending? Because a smaller ending is strictly more useful — anything that can be appended to a subsequence ending in 9 can also be appended to one ending in 3, but not the other way round. Among all subsequences of a given length, the one with the smallest tail dominates all the others, so it is the only one worth remembering.

For each new value x:

- If x is larger than every tail, it extends the longest run we have: append it, and the answer grows by one.
- Otherwise, find the leftmost tail that is greater than or equal to x and overwrite it with x. This says: there is now a subsequence of that length ending in something smaller, which is a strict improvement for the future and costs nothing in the present.
python
from bisect import bisect_left

def length_of_lis(nums):
    tails = []
    for x in nums:
        pos = bisect_left(tails, x)        # leftmost index with tails[pos] >= x
        if pos == len(tails):
            tails.append(x)                # x extends the longest run
        else:
            tails[pos] = x                 # x improves an existing length
    return len(tails)

Two facts make this work, and both deserve a moment.

tails is always sorted. A subsequence of length 3 contains, inside it, a subsequence of length 2 ending at a strictly smaller value, so the best length-2 tail can only be smaller than the best length-3 tail. Sortedness is what lets us binary-search, which is where the log N comes from.

Overwriting never breaks anything. Replacing tails[pos] does not destroy a subsequence we might still need, because the length recorded at that position is unchanged and its ending only got smaller — strictly more permissive going forward.

Crucial Notetails is not the increasing subsequence. Its length is correct, but its contents can be a mixture of values from different subsequences that never coexisted. On [10, 9, 2, 5, 3, 7, 101, 18] the array ends as [2, 3, 7, 18], which happens to be valid here; on other inputs it is not. If the actual subsequence is required, keep parent pointers alongside, or use the O(N²) table where reconstruction is straightforward. Claiming tails as the answer sequence is a classic interview stumble.

For strictly increasing we use bisect_left; for the non-decreasing variant, where equal values are allowed, use bisect_right. That single character is the whole difference.

Where this shows up

The recognition signal is broader than "increasing numbers". Reach for this whenever a problem asks for the longest chain of items where each one must beat the previous one on some ordering, and items may be skipped.

Concretely: stacking boxes that must fit inside one another, chains of pairs, scheduling non-overlapping intervals — many of these reduce to this shape after a sort, or to its mirror image. A two-dimensional version, where each item must beat the previous one on two keys at once, becomes exactly this once you sort on one key and run the chain on the other.

Two portable lessons to keep:

When a state does not determine the future, add whatever is missing — often "what does it end with?" — and accept that the answer becomes an aggregate over the table rather than one cell.

When you keep a set of candidates, ask whether some of them dominate others. Here, among all subsequences of a given length, only the one with the smallest tail could ever matter. Throwing away dominated candidates is what collapsed a quadratic scan into a binary search, and the same move appears all over algorithm design.

Exponential Try Every Subsequence
→
O(N²) Time · O(N) Space Table
→
O(N log N) Time · O(N) Space Patience Tails