Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Longest Increasing Subsequence with Dynamic Programming

The longest increasing subsequence problem rarely announces itself as a computer science exercise, but it hides in places where you work with sequences of numbers and want the longest run of improvement. Given a list of values in a fixed order, the task is to find the longest selection of those values that keeps the original order while each chosen value is strictly greater than the one before it. Strictness matters here: a run of equal readings does not count, unless you deliberately relax the comparison to allow equal values, which yields a non-decreasing subsequence instead.

The difference between a subsequence and a contiguous run is where the problem earns its keep. Take the list [10, 9, 2, 5, 3, 7, 101, 18]. A contiguous increasing stretch of length three exists (2, 5, 7), yet the longest increasing subsequence has length four: 2, 5, 7, 101. Skipping the unhelpful values is what buys the extra length.

The everyday version of the problem arrives without any programming attached. Consider a year of daily maximum temperatures logged at a Bureau of Meteorology station in Melbourne: the longest stretch of days on which each afternoon was warmer than the last is precisely an increasing subsequence of those readings. The same shape shows up when a Sydney retailer wants the longest run of improving weekly sales, when a wool buyer tracks rising micron values across auction results, or when a logistics planner studies a year of promised delivery windows for Brisbane customers. In every case the underlying question is the same: which subsequence, in order, rises the longest?

What the longest increasing subsequence actually asks

Formally, you are handed a sequence of comparable values and asked for the maximum length of a subsequence whose elements increase strictly. The subsequence must respect the original ordering, but it may skip any number of elements. Two small decisions change the answer, so state them explicitly before coding. First, is the comparison strict (a[j] < a[i]) or non-strict (a[j] <= a[i])? Second, must the chosen elements be adjacent in the input, or may they be spread out?

Once those are settled, the problem has an appealing symmetry with other sequence work: there is a natural way to define a state for each position, and the answer for that position depends only on states that come earlier. That property is exactly what dynamic programming exploits, and it is why the technique transfers so cleanly to variations such as longest non-decreasing subsequence, longest common subsequence, and maximum-length chain problems that share the same underlying structure.

Consider the contrast with a greedy pass. A greedy approach tries to commit to the smallest viable value and extend it, which sounds economical but loses information: with [4, 3, 6, 5, 7] a greedy chain anchored at 3 never recovers the length that a chain anchored at 2 in the classic example would. Dynamic programming keeps every candidate alive, which costs memory but preserves the option to choose better later.

The dynamic programming recurrence

Define dp[i] as the length of the longest increasing subsequence that ends at index i. The base case is dp[i] = 1, because any single element forms a valid subsequence of length one. For every earlier index j where a[j] < a[i], the value at i can extend the best chain that ends at j, giving the recurrence dp[i] = 1 + max(dp[j]) over all such j, or 1 when no such j exists.

The justification is short but worth stating. Any increasing subsequence ending at i either contains only a[i], or contains some earlier element a[j] with a[j] < a[i] immediately before it in that subsequence. The prefix up to that j cannot be longer than dp[j], otherwise we could splice in a longer prefix and contradict the definition of dp[j]. So the best possible chain ending at i has length exactly one more than the best chain ending at a qualifying j. The final answer is the maximum value across the whole array, not the last entry, since the longest chain might finish anywhere.

In pseudocode, the shape is compact:

dp = array of n ones
for i in 0 .. n-1:
    for j in 0 .. i-1:
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
answer = max(dp)

Notice that the inner loop only looks backwards. Each dp[i] is finalised before it is used, which means the state definition is self-consistent and the recurrence can be evaluated in a single forward sweep with no recursion, no memoisation dictionary, and no risk of exponential blow-up.

Tracing the recurrence by hand

Running the pseudocode over [10, 9, 2, 5, 3, 7, 101, 18] produces the following states, with the predecessor column recording which index each chain was extended from.

i value dp[i] predecessor
0 10 1 –
1 9 1 –
2 2 1 –
3 5 2 2
4 3 2 2
5 7 3 3
6 101 4 5
7 18 4 5

Two chains of length four exist, 2, 5, 7, 101 and 2, 5, 7, 18. The predecessor column lets you walk backwards from any index and rebuild the actual subsequence, which is the step most write-ups skip and most real tasks need. Tracing also exposes the intuition behind the recurrence: at index 7 the value 18 cannot extend the chain ending at 10 or 9, but it happily extends the chain ending at 7, so the length stays at four.

This trace is cheap to do by hand precisely because the state definition is simple. Students who prefer to see the mechanics visually can compare the table above with a stack of index cards, each card carrying a length and a pointer to the card beneath it.

A Python implementation you can reuse

The direct translation of the recurrence is short enough to memorise, and it returns the subsequence itself rather than only its length:

def longest_increasing_subsequence(values):
    n = len(values)
    if n == 0:
        return []
    dp = [1] * n
    parent = [-1] * n
    for i in range(n):
        for j in range(i):
            if values[j] < values[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                parent[i] = j
    best = max(range(n), key=lambda i: dp[i])
    chain = []
    while best != -1:
        chain.append(values[best])
        best = parent[best]
    chain.reverse()
    return chain

If any part of the syntax is unfamiliar, the community notes on Python programming cover list handling, comprehensions, and the standard library pieces this code leans on. A quick sanity check with assert longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18]) == [2, 5, 7, 18] confirms both the length and the ordering of the returned chain.

A common follow-up asks for the count of distinct longest subsequences rather than one of them, which is solved by summing dp[j] + 1 == dp[i] contributions across all qualifying j instead of merely recording one predecessor. Another follow-up asks for the count of non-decreasing subsequences, where the comparison relaxes to <= and the base case stays at one.

The greedy alternative with binary search

There is a faster family of solutions that never revisits an earlier position in the way the quadratic version does. The trick is to maintain a list called tails, where tails[k] holds the smallest possible ending value of an increasing subsequence of length k + 1 found so far. For each new value, binary search finds the first position in tails whose value is greater than or equal to it, and the value is placed there, replacing a larger ending value with a more useful one. The final length of tails is the answer.

from bisect import bisect_left

def lis_length(values):
    tails = []
    for value in values:
        pos = bisect_left(tails, value)
        if pos == len(tails):
            tails.append(value)
        else:
            tails[pos] = value
    return len(tails)

This runs in O(n log n) time and O(n) space, which matters when the input is large. Its correctness argument rests on a greedy invariant rather than a recurrence: keeping the smallest possible tail leaves the most room for future values to extend a chain. Readers who enjoy comparing a greedy rule with a dynamic programming one can set the two side by side using the Prim's algorithm tutorial, which commits to the cheapest available edge and never looks back, but reaches its justification through a very different exchange argument.

One caveat deserves emphasis: tails is not itself a subsequence. It stores the best tail for each length, and those tails may come from different positions, so reconstructing the actual chain needs extra bookkeeping. If you only need the length, the binary search version is the right tool; if you need the values, the quadratic version with a predecessor array is simpler to trust.

Complexity and where the problem shows up in Australia

The quadratic algorithm costs O(n²) time and O(n) space, which is comfortable for a few thousand elements and painful for a few hundred thousand. The binary search version reduces the time to O(n log n) with the same linear space, and it can be made space-efficient by discarding the tails history. For comparison, the site's algorithms hub collects the neighbouring topics worth knowing alongside this one, from binary search trees to data structures and visualisations.

The commercial setting for this kind of analysis is closer to home than it might appear. An Australian online retailer running warehouses in Melbourne and Brisbane forecasts demand per product line, and those forecasts decide how much stock moves through each site. Choosing FIFO rotation for aged inventory means the order in which lines leave the warehouse can be scored as an increasing subsequence of how long they have been sitting there. A wool buyer tracking micron readings across auction results wants the longest rising run of quality values before the market turns. Even a consumer app that ranks nearby cafes for a late arvo coffee can rank candidates by the longest chain of monotonically improving opening times.

Those forecasts also run into regulatory reality. Once customer order histories feed the analysis, the Privacy Act 1988 and the Australian Privacy Principles limit how personal information may be collected, combined, and reused, and any notifiable data breach carries mandatory reporting obligations. Accuracy carries commercial weight too, since Australian Consumer Law guarantees mean an availability or pricing promise that the data did not support is a genuine compliance exposure, not just a missed sale.

Traps to avoid and ways to practise

Most bugs in this problem come from the boundary conditions rather than the recurrence itself, so it pays to run the following checks before trusting an implementation:

The following exercises cover the variants that show up in interviews and in practice:

Dynamic programming turns this problem into a matter of defining one state per position and letting the states talk to each other in order. The recurrence is a two-line rule, the reconstruction is a walk backwards through parent pointers, and the faster binary search version trades a little conceptual weight for a large gain in running time.