最长递增子序列

Code

/**
 * 求最长递增子序列
 */
function LIS(nums: number[]) {

}
// 期望 [1, 2, 3, 6, 9]
console.log(LIS(4, 5, 1, 2, 7, 3, 6, 9))

解析

function LIS(nums: number[]) {
  if (nums.length === 0) {
    return []
  }
  const dp = [[nums[0]]];

  for (let i = 1; i < nums.length; i ++) {
    const num = nums[i];
    _update(num)
  }

  function _update(num) {
    for (let i = dp.length - 1; i >= 0 ; i -- ) {
      const line = dp[i];
      const last = line[line.length - 1];
      if (num > last) {
        dp[i + 1] = [...line, num];
        break;
      } else if (num < last && i === 0) {
        dp[i] = [num];
      }
    }
  }

  return dp[dp.length - 1];
}