题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

测试用例

示例 1：

• 输入：nums = [10,9,2,5,3,7,101,18]
• 输出：4
• 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4

示例 2：

• 输入：nums = [0,1,0,3,2,3]
• 输出：4

示例 3：

• 输入：nums = [7,7,7,7,7,7,7]
• 输出：1

思路

动态规划，参考代码中的注释

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  let n = nums.length;
  let dp = new Array(n).fill(1);
  let res = 0;

  // dp[i]表示长度为i的序列的最长递增子序列为dp[i]；
  // 比如长度为1的序列 最长递增子序列为dp[1] = 1
  // 所有长度大于等于1的序列 最长递增子序列的长度初始化都为1

  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      // 遍历长度为i的序列
      // 拿当前值j与序列末尾值比较
      // 如果满足递增了 —— 看要不要当前值j
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    res = Math.max(res, dp[i]);
  }

  return res;
};

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入数组nums: ");
const nums = readline()
  .split(",")
  .map((item) => parseInt(item));

const res = lengthOfLIS(nums);
console.log("结果为: ", res);

/* 
  请输入数组nums:
  10,9,2,5,3,7,101,18
  结果为:  4

  请输入数组nums:
  0,1,0,3,2,3
  结果为:  4

  请输入数组nums:
  7,7,7,7,7,7,7
  结果为:  1
*/