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

// DP O(n²) — the classic, good enough for interviews
function lengthOfLIS(nums: number[]): number {
  const n = nums.length
  if (n === 0) return 0  // empty array → LIS = 0 (avoids Math.max(...[]) = -Infinity)
  // dp[i] = length of the LIS ending at index 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] can extend the subsequence ending at nums[j]
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
  }
  return Math.max(...dp)
}