Longest Increasing Subsequence

The previous lesson aligned two sequences. Now we ask a question about a single one. Given an array $a[\mathrm{1..}n]$ of numbers, a longest increasing subsequence (LIS) is a longest set of positions $i_1<i_2<\cdots <i_k$ whose values strictly increase, $a[i_1]<a[i_2]<\cdots <a[i_k]$. As with LCS, the word is subsequence, not substring: the chosen elements keep their original order but need not be contiguous. In $a=[3,1,4,1,5,9,2,6]$ the subsequence $[3,4,5,9]$ increases and has length $4$, and no longer one exists, so the LIS length is $4$.¹

Plot the values against their positions and an LIS is a longest chain of points that climbs as it moves right, never stepping down:

A brute-force scan over all $2^n$ subsequences is hopeless. But LIS has clean optimal substructure, the same property behind every dynamic program, and it admits two algorithms worth knowing well: a direct $O(n^2)$ dynamic program, and a faster $O(n\log n)$ method built on patience sorting.

The $O(n^2)$ dynamic program: subsequences that end here

The decisive modeling move, the analog of LCS's index by prefix, is to index each subproblem by the element its subsequence is forced to end at. Anchoring the endpoint is what makes the pieces compose: an increasing subsequence ending at $i$ is some shorter increasing subsequence ending at an earlier, smaller element, with $a[i]$ tacked on.

Every increasing subsequence ends somewhere, so the answer is ${\max }_{1\le i\le n}L[i]$, not $L[n]$, a small but important distinction from the prefix DPs, where the answer sat in the last cell.

To extend a subsequence so that it ends at $i$, look at all earlier indices $j<i$ whose value is smaller than $a[i]$; any increasing subsequence ending at such a $j$ can be lengthened by appending $a[i]$. We take the best such predecessor, or start fresh with just $a[i]$ if none exists:

The $\{0\}$ guarantees the $\max$ is defined and yields $L[i]=1$ when no smaller predecessor exists: the subsequence consisting of $a[i]$ alone.

Each $L[i]$ scans the $i-1$ earlier indices, so the fill is ${\sum }_i(i-1)=\Theta (n^2)$ time and $\Theta (n)$ space.

Reconstruction. The $prev$ array is a forest of parent pointers: to recover an actual LIS, find the index $best$ maximizing $L$, then follow $prev$ backwards until it hits nil, reversing the collected indices. This costs $O(k)\le O(n)$, cheap beside the fill.

The blue endpoints form the recovered chain: starting at the best $L=4$ cell (index $6$, value $9$) and hopping along $prev$ visits indices $6\to 5\to 3\to 1$, whose values $9,5,4,3$ reverse to the LIS $3,4,5,9$.

The solid chain $3\to 4\to 5\to 9$ (indices $1,3,5,6$) realizes $L=4$ at index $6$, and the row beneath records every $L[i]$. A subtlety: the predecessor of $4$ is not unique — both the $3$ (index $1$) and the $1$ (index $2$) are smaller and end a length-$1$ run, so either could precede it. Reconstruction is greedy: it stores and follows a single parent, and we take the earlier index, giving $3,4,5,9$. The dotted arrows mark the other choices: extending the $1$ at index $2$ instead yields $1,4,5,9$, and stopping at the $6$ (index $8$, also $L=4$) yields $3,4,5,6$. Whenever $prev$ has ties or several endpoints reach the maximum length, the LIS is simply not unique.

from typing import Optional, Sequence, TypeVar

from comparable import Comparable

# any totally-ordered element works (ints, floats, strings, tuples).
Value = TypeVar("Value", bound=Comparable)

def lis_length(values: Sequence[Value], strict: bool = True) -> int:
  """
    Length of a longest increasing subsequence of `values`.\n
    With `strict` False, equal adjacent values are allowed (longest\n
    non-decreasing subsequence).\n
  """
  return len(lis_subsequence(values, strict=strict))

def lis_subsequence(
  values: Sequence[Value], strict: bool = True
) -> list[Value]:
  """
    An actual longest increasing subsequence of `values`, reconstructed by\n
    following parent pointers from the best endpoint. Ties are broken toward\n
    the earlier predecessor, matching the lesson's greedy reconstruction.\n
    With `strict` False, the run may be non-decreasing.\n
  """
  count: int = len(values)
  if count == 0:
    return []

  # length[i] = longest run ending exactly at i; parent[i] = its predecessor.
  length: list[int] = [1 for _ in range(count)]
  parent: list[Optional[int]] = [None for _ in range(count)]

  for index in range(count):
    for earlier in range(index):

      # non-strict `earlier <= index` as `not (index < earlier)`, so the
      # element only needs `<` (the Comparable protocol bound on Value).
      precedes: bool = (
        values[earlier] < values[index]
        if strict
        else not (values[index] < values[earlier])
      )

      # extend through `earlier` when it yields a strictly longer run.
      if precedes and length[earlier] + 1 > length[index]:
        length[index] = length[earlier] + 1
        parent[index] = earlier

  # best endpoint is the cell with the greatest run length.
  best_endpoint: int = max(range(count), key=lambda index: length[index])

  # walk parent pointers back, then reverse into forward order.
  chain: list[Value] = []
  cursor: Optional[int] = best_endpoint
  while cursor is not None:
    chain.append(values[cursor])
    cursor = parent[cursor]

  chain.reverse()
  return chain

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

The $O(n\log n)$ method: patience sorting and the tails array

The quadratic inner loop searches all earlier indices for the best predecessor. To remove it, stop tracking endpoints individually and instead maintain, for each achievable length, the single most useful witness.

The whole algorithm is one pass. For each element $x=a[i]$, binary-search$tails$ for the first entry $\ge x$ (a lower_bound). If one is found, overwrite it with $x$; if none is (so $x$ exceeds every tail), append $x$. The LIS length is the final length of $tails$.

Each element costs one $O(\log n)$ binary search, for $O(n\log n)$ total.

Why this is correct

Two facts carry the whole proof. First, $tails$ is always sorted in increasing order, so binary search is valid. Second, the updates never reduce any achievable length, so the array's length tracks the true LIS.

Each row is $tails$ after one more element, with the just-written cell in blue and the append-or-overwrite verdict on the right. Adding $2$ overwrites the $4$ (the first tail $\ge 2$): the length-$2$ run now ends at the smaller value $2$, leaving room for future growth without shortening the array. The final $tails=[1,2,5,6]$ has length $4$, matching the LIS length. The values in that last row are not themselves an LIS — $[1,2,5,6]$ never occurs in order — but their count matches the LIS length, and the index-tracking below recovers a genuine subsequence.

The one non-trivial step in each iteration is the placement itself: given the sorted array $tails$ and the incoming $x$, find the first entry $\ge x$. Because $tails$ is sorted, this lower_bound is a textbook binary search, halving the live window each probe. Adding $2$ into $tails=[1,4,5,9]$ runs as follows.

The search never inspects the whole array: the first probe rules out the right half, so index $1$ is confirmed as the target after $O(\log |tails|)=O(\log n)$ comparisons. Overwriting the $4$ with the smaller $2$ keeps the length-$2$ tail as small as possible.

Reconstruction in $O(n\log n)$. As written, $tails$ holds values, not positions, so it loses the actual subsequence. To recover it, store indices: let $tailIdx[k]$ hold the position whose value is $tails[k]$, and on each step record $parent[i]=tailIdx[k-1]$ (the index then sitting one pile to the left). Following $parent$ back from $tailIdx[\text{last}]$ reconstructs an LIS, exactly as in the quadratic version.

from bisect import bisect_left, bisect_right
from typing import Optional, Sequence, TypeVar

from comparable import Comparable

Value = TypeVar("Value", bound=Comparable)

def lis_length_fast(values: Sequence[Value], strict: bool = True) -> int:
  """
    Length of a longest increasing subsequence in O(n log n).\n
    With `strict` True the run is strictly increasing (a `lower_bound`\n
    overwrite); with `strict` False it may be non-decreasing (an\n
    `upper_bound` overwrite, so equal elements extend rather than replace).\n
  """
  tails: list[Value] = []
  for element in values:

    # lower_bound for strict, upper_bound for non-decreasing.
    position: int = (
      bisect_left(tails, element) if strict else bisect_right(tails, element)
    )

    # append a new pile or overwrite the first tail >= element.
    if position == len(tails):
      tails.append(element)
    else:
      tails[position] = element

  return len(tails)

def lis_subsequence_fast(
  values: Sequence[Value], strict: bool = True
) -> list[Value]:
  """
    An actual longest increasing subsequence in O(n log n), recovered by\n
    storing the index that lands in each pile and a parent pointer to the\n
    index then sitting one pile to its left.\n
  """
  count: int = len(values)
  if count == 0:
    return []

  # tails holds values for the binary search; tail_index mirrors their indices.
  tails: list[Value] = []
  tail_index: list[int] = []
  parent: list[Optional[int]] = [None for _ in range(count)]

  for index in range(count):
    element: Value = values[index]
    position: int = (
      bisect_left(tails, element) if strict else bisect_right(tails, element)
    )

    # the index one pile to the left becomes this element's predecessor.
    parent[index] = tail_index[position - 1] if position > 0 else None
    if position == len(tails):
      tails.append(element)
      tail_index.append(index)
    else:
      tails[position] = element
      tail_index[position] = index

  # the last pile's index is the endpoint of a longest run.
  chain: list[Value] = []
  cursor: Optional[int] = tail_index[-1]
  while cursor is not None:
    chain.append(values[cursor])
    cursor = parent[cursor]
  chain.reverse()
  return chain

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

Variants on the same machine

Both algorithms adapt to a family of related problems with small edits.

Longest non-decreasing subsequence. To allow equal adjacent values ($a[i_1]\le a[i_2]\le \cdots$), change lower_bound to upper_bound: search for the first tail strictly greater than $x$. An equal element then extends rather than overwrites, giving the non-strict relaxation. (In the $O(n^2)$ DP, change the test $a[j]<a[i]$ to $a[j]\le a[i]$.)

Counting the number of LIS. Alongside $L[i]$ track $cnt[i]$ = the number of longest increasing subsequences ending at $i$. When a strictly better predecessor $j$ is found ($L[j]+1>L[i]$), reset $cnt[i]\leftarrow cnt[j]$; when a tying predecessor is found ($L[j]+1=L[i]$), accumulate $cnt[i]+=cnt[j]$. The answer sums $cnt[i]$ over all $i$ achieving the global maximum $L[i]$. Speeding this counting variant to $O(n\log n)$ uses a Fenwick or segment tree keyed by value to roll up best-length-and-count over smaller predecessors.²

Russian doll envelopes. Each envelope has width $w$ and height $h$, and one nests in another only if both dimensions are strictly larger; find the longest nesting chain. Reduce to LIS in two dimensions: sort by width ascending, and break ties by height descending, then run LIS on the height sequence alone. The descending tiebreak is what makes this valid: among envelopes of equal width, the descending order makes it impossible for two of them to both appear in an increasing height run (their heights decrease), so we never illegally nest two equal-width envelopes. With distinct widths this reduces a 2-D nesting to a plain 1-D LIS, solvable in $O(n\log n)$.³

Bitonic and longest decreasing. A longest decreasing subsequence is just LIS on the reversed comparison (or on the negated array). A longest bitonic subsequence, one that increases then decreases, is computed by running the ending-here LIS left-to-right to get $L[i]$ and a symmetric decreasing pass right-to-left to get $R[i]$; the best bitonic peak at $i$ has length $L[i]+R[i]-1$.

On $[1,3,5,4,2]$ the peak sits at the value $5$: three elements climb up to it ($1,3,5$) and three descend from it ($5,4,2$), and the $-1$ avoids double-counting the peak, so the whole array is one bitonic run of length $5$.

from typing import Sequence, TypeVar

from comparable import Comparable

Value = TypeVar("Value", bound=Comparable)

def count_lis(values: Sequence[Value]) -> int:
  """
    The number of distinct longest strictly-increasing subsequences of\n
    `values`. An empty sequence has a single (empty) LIS.\n
  """
  count_total: int = len(values)
  if count_total == 0:
    return 1

  # length[i] = longest run ending at i; count[i] = how many such runs.
  length: list[int] = [1 for _ in range(count_total)]
  count: list[int] = [1 for _ in range(count_total)]

  for index in range(count_total):
    for earlier in range(index):
      if values[earlier] >= values[index]:
        continue

      # a strictly longer run through `earlier`: adopt its count.
      if length[earlier] + 1 > length[index]:
        length[index] = length[earlier] + 1
        count[index] = count[earlier]

      # another run of the same best length: add its ways in.
      elif length[earlier] + 1 == length[index]:
        count[index] += count[earlier]

  best_length: int = max(length)
  return sum(
    count[index]
    for index in range(count_total)
    if length[index] == best_length
  )

from bisect import bisect_left
from typing import NamedTuple, Sequence

class Envelope(NamedTuple):
  """
    One envelope's outer dimensions: its width and its height.\n
  """
  width: int
  height: int

def max_envelopes(envelopes: Sequence[Envelope]) -> int:
  """
    Length of the longest chain of envelopes that nest strictly inside one\n
    another (both dimensions strictly increasing).\n
  """
  if not envelopes:
    return 0

  # width ascending; on equal width, height descending (the nesting trick).
  ordered: list[Envelope] = sorted(
    envelopes, key=lambda envelope: (envelope.width, -envelope.height)
  )

  # strict LIS over the height column via the tails array.
  tails: list[int] = []
  for envelope in ordered:

    # append a new pile or overwrite the first tail >= this height.
    position: int = bisect_left(tails, envelope.height)
    if position == len(tails):
      tails.append(envelope.height)
    else:
      tails[position] = envelope.height

  return len(tails)

from typing import Sequence, TypeVar

from comparable import Comparable

Value = TypeVar("Value", bound=Comparable)

def _ending_increasing_lengths(values: Sequence[Value]) -> list[int]:
  """
    `result[i]` = length of the longest strictly-increasing run ending at i.\n
  """
  count: int = len(values)
  lengths: list[int] = [1 for _ in range(count)]

  # extend each cell from the best smaller earlier element.
  for index in range(count):
    for earlier in range(index):
      if values[earlier] < values[index]:
        lengths[index] = max(lengths[index], lengths[earlier] + 1)

  return lengths

def longest_decreasing_subsequence_length(values: Sequence[Value]) -> int:
  """
    Length of a longest strictly-decreasing subsequence: the increasing run\n
    on the reversed sequence.\n
  """
  reversed_values: list[Value] = list(reversed(values))
  lengths: list[int] = _ending_increasing_lengths(reversed_values)
  return max(lengths, default=0)

def longest_bitonic_subsequence_length(values: Sequence[Value]) -> int:
  """
    Length of a longest bitonic subsequence — one that strictly increases up\n
    to a single peak, then strictly decreases. A lone element (and the empty\n
    sequence's 0) count as degenerate bitonic runs.\n
  """
  count: int = len(values)
  if count == 0:
    return 0

  # increasing[i] ends at i; decreasing[i] is the increasing run on the
  # reversed suffix, re-indexed forward, so it starts at i.
  increasing: list[int] = _ending_increasing_lengths(values)
  reversed_lengths: list[int] = _ending_increasing_lengths(
    list(reversed(values))
  )
  decreasing: list[int] = list(reversed(reversed_lengths))

  return max(
    increasing[index] + decreasing[index] - 1 for index in range(count)
  )

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

Lower bounds, permutations, and a longer view

The $O(n\log n)$ patience-sorting bound is essentially optimal. Fredman (1975) proved that any comparison-based LIS algorithm needs $\Omega (n\log n)$ comparisons in the worst case, so the tails-array method is asymptotically the best achievable under comparisons — the binary search is forced. Only by dropping to the integer-RAM model (values in a bounded range, van Emde Boas or $y$-fast tries in place of binary search) can one shave the bound to $O(n\log \log n)$; the bounded-gap variant Longest Increasing Subsequence II requires a segment tree over the value axis instead of a plain tails array.

Patience sorting also appears in probability. Hammersley asked in 1972 how long the LIS of a random permutation of $\{1,\dots ,n\}$ tends to be; the answer, $\approx 2\sqrt{n}$, was determined by Logan and Shepp and by Vershik and Kerov (1977), and the full limiting distribution of the fluctuations — the Tracy–Widom distribution from random-matrix theory — was found by Baik, Deift, and Johansson (1999). That an interview-style array problem shares its scaling law with the largest eigenvalue of a random Hermitian matrix is one of the more surprising connections in combinatorics, and patience sorting is the constructive object underneath it (Aldous and Diaconis's 1999 survey Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem is the readable entry point).⁴

The chain/antichain duality noted above (Mirsky and Dilworth) is the reason LIS generalizes cleanly to partial orders: Russian-doll envelopes, box-stacking (Maximum Height by Stacking Cuboids), and job-nesting are all longest chain in a poset problems, and the sort-then-LIS reduction works precisely when the poset can be linearized on one coordinate so that the residual constraint is one-dimensional. When it cannot — three or more strictly-independent dimensions — the problem becomes a longest chain in higher-dimensional dominance order, solvable with a $k$-dimensional Fenwick tree in $O(n{\log }^{k-1}n)$, the direct descendant of the Fenwick-tree counting that speeds up the LIS-counting variant.

Takeaways

• The LIS is a longest strictly-increasing subsequence (order preserved, contiguity not required), not a substring.
• The $O(n^2)$ DP indexes by the ending index: $L[i]=1+\max \{L[j]:j<i,a[j]<a[i]\}$, the answer is ${\max }_{i}L[i]$, and parent pointers reconstruct the subsequence.
• The $O(n\log n)$ method keeps a sorted tails array where $tails[k]$ is the smallest tail of a length-$(k+1)$ run; each element triggers a lower_bound overwrite-or-append. Overwriting with a smaller tail never loses an achievable length, so $|tails|$ is the LIS length; this is patience sorting.
• Variants reuse the same algorithms: upper_bound for non-decreasing, parallel counts for the number of LIS, sort-then-LIS with a descending tiebreak for Russian-doll envelopes, and forward+backward passes for bitonic.
• LIS equals the minimum antichain (decreasing-subsequence) cover, the pile count, a constructive instance of Mirsky's theorem.