300. Longest Increasing Subsequence

Return the length of the longest strictly increasing subsequence of nums.

tails[k] = the smallest possible tail of an increasing subsequence of length k+1. For each x, binary-search the first tail ≥ x and replace it, or append x if none exists.

1function lengthOfLIS(nums: number[]): number {
2  const tails: number[] = [];
3  for (const x of nums) {
4    let lo = 0, hi = tails.length;
5    while (lo < hi) {
6      const mid = (lo + hi) >> 1;
7      if (tails[mid] < x) lo = mid + 1;
8      else hi = mid;
9    }
10    tails[lo] = x;
11  }
12  return tails.length;
13}

nums

101

tails

empty

tails is empty.

1 / 0

Space: play/pause · ←/→: step