Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumone-dimensional-dp

Longest Increasing Subsequence

Problem (restated)

Return length of the longest strictly increasing subsequence.

Intuition

Maintain smallest tail of all increasing subsequences of each length; binary search place for each num.

Approaches

Patience sorting (tails)

Unverified

Time O(n log n)Space O(n)

Idea. tails[len-1] = smallest tail for length len; lower_bound replace or append.

Walkthrough. [10,9,2,5,3,7,101,18] → length 4 (2,3,7,101).

Trade-offs. O(n²) DP is simpler; patience is faster.

Solution

export function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid]! < x) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(x);
    else tails[lo] = x;
  }
  return tails.length;
}

export function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid]! < x) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(x);
    else tails[lo] = x;
  }
  return tails.length;
}

Template connection

1D DP / binary search on answer structure.

Reflection

tails stores the smallest tail of every length. A new value replaces one tail or extends the array. The answer is the length, not the values.
The sequence is strictly increasing, so an equal value does not extend a tail. A decreasing array answers 1.
tails is not the subsequence. The O(n²) DP returns the same length. This pass is O(n log n).