Dãy Con Tăng Dài NhấtLongest Increasing Subsequence

// DP O(n²) — kinh điển, đủ cho phỏng vấn
function lengthOfLIS(nums: number[]): number {
  const n = nums.length
  if (n === 0) return 0  // mảng rỗng → LIS = 0 (tránh Math.max(...[]) = -Infinity)
  // dp[i] = độ dài LIS kết thúc tại vị trí i
  const dp = new Array(n).fill(1)

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        // nums[i] có thể nối sau nums[j]
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
  }
  return Math.max(...dp)
}