Longest Increasing Subsequence

Find the longest strictly increasing subsequence. Values do not need to be next to each other.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Longest Increasing Subsequence: For every achievable length, retain the smallest ending value found so far.

Input and goalFind the longest strictly increasing subsequence. Values do not need to be next to each other.

Initialize empty tailsBefore reading nums, smallest_end is empty; the first bisect position is slot 0.

10input i=09253710118-bisect slot=0-------

examplenums = [10, 9, 2, 5, 3, 7, 101, 18]rowAxistop = nums; bottom = smallest_end slots for lengths 1..8nextValue10tails[]operationstart

Recognize it

The problem asks only for the length of a strictly increasing subsequence in a long array, suggesting O(n log n) tail compression rather than quadratic pair DP.

Keep true

After each input prefix, smallest_end[k] is the minimum possible tail of any increasing subsequence of length k+1 in that prefix, and the tail array is increasing.

Reuse it

Keep the most permissive representative for every achieved progress level; the same dominance idea prunes states in scheduling, envelopes, and frontier DP.

Pattern: Keep the smallest possible end for each length.

Simple idea: smallest_end[i] is the smallest ending value found for an increasing subsequence of length i + 1. Replace the first ending value that is not smaller than the new value. A smaller ending value gives future values more room.

from bisect import bisect_left

def length_of_lis(nums: list[int]) -> int:
   smallest_end: list[int] = []
   for num in nums:
      index = bisect_left(smallest_end, num)
      if index == len(smallest_end):
         smallest_end.append(num)
      else:
         smallest_end[index] = num
   return len(smallest_end)

Cost: $O(n\log n)$ time and $O(n)$ space.