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.