AlgoScope

Longest Increasing Subsequence

O(n^2) DP over predecessors, or O(n log n) with patience sorting and binary search.

Dynamic programming, algorithm, intermediateAlso called LIS
Index 1 has a chain of length 1.10091225334751016187i
Index 1 has a chain of length 1.10091225334751016187i

DP in One Row: Longest increasing subsequence

Decision, step 3 of 10

9: nothing before it is smaller, so no chain can take it. len[1] = 1.

How dp in one row works

Cost

Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)

Quadratic variant is O(n^2).

Before this

Variants

  • O(n^2) DPBest ending at each index.
  • Patience SortingBinary search into the tails array.

Taught by the same lesson

DP in One Row covers these too, in the same run.