Longest Increasing Subsequence (LIS) — vì sao có thể giải O(n log n) thay vì O(n²)?

Ý tưởng O(n²): dp[i] = độ dài LIS kết thúc tại i; với mỗi i quét lại các j < i có nums[j] < nums[i].

Tăng tốc O(n log n) — patience sorting: giữ một mảng tails, tails[k] = phần tử kết nhỏ nhất của một dãy tăng độ dài k+1. Với mỗi số, dùng binary search tìm vị trí thay thế (hoặc nối thêm). Độ dài tails chính là độ dài LIS.

Hình dung: xếp bài patience — đặt lá lên chồng đầu tiên có lá đỉnh ≥ lá mới; số chồng = LIS.

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
    }
    tails[lo] = x // thay thế hoặc nối thêm khi lo === length
  }
  return tails.length
}

Độ phức tạp: O(n log n) thời gian, O(n) bộ nhớ.

Lưu ý: tails không phải là LIS thực tế — nó chỉ giữ đúng độ dài. Muốn truy vết dãy thật phải lưu thêm con trỏ cha.

O(n²) idea: dp[i] = LIS length ending at i; for each i rescan all j < i with nums[j] < nums[i].

O(n log n) speedup — patience sorting: keep a tails array where tails[k] = the smallest possible tail of an increasing subsequence of length k+1. For each number, binary search for its replacement position (or append). The length of tails is the LIS length.

Picture it: dealing patience cards — place each card on the first pile whose top ≥ the new card; the number of piles = LIS.

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
    }
    tails[lo] = x // replace, or append when lo === length
  }
  return tails.length
}

Complexity: O(n log n) time, O(n) space.

Note: tails is not the actual LIS — it only preserves the correct length. Reconstructing the real sequence needs extra parent pointers.