最长递增子序列

题目

题目来源：力扣（LeetCode）

给你一个整数数组 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

思路分析

动态规划

• 状态定义

定义dp[i] ，表示在nums数组的前 i 个元素中，以 nums[i] 结尾的最长上升子序列的长度。注意：这个定义中 nums[i] 必须被选取，且必须是这个子序列的最后一个元素；

• 状态转移方程

我们从小到大计算 dp 数组的值，在计算dp[i] 之前，我们已经计算出 dp[0 … i - 1] 的值，则状态转移方程为：

dp[i] = max(dp[i], dp[j] + 1), 其中0 ≤ j < i且 num[j] < num[i]

即考虑往 dp[0 … i - 1] 中最长的上升子序列后面再加一个 nums[i]。由于 dp[j] 代表 nums[0, … , j] 中以 nums[j] 结尾的最长上升子序列，所以如果能从 dp[j] 这个状态转移过来，那么 nums[i] 必然要大于 nums[j]，才能将 nums[i] 放在 nums[j] 后面以形成更长的上升子序列。

• 初始状态

dp[i] = 1，其含义是nums的每个元素都至少可以单独成为子序列，此时长度都为1

• 返回值

返回dp列表中的最大值，即可得到全局的最长上升子序列的长度

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  let dp = new Array(nums.length);
  let ans = 0;
  for (let i = 0; i < nums.length; i++) {
    // 初始化 dp[i] 为 1，表示 nums 的每个元素都至少可以单独成为子序列，此时长度都为 1
    dp[i] = 1;
    for (let j = 0; j < i; j++) {
      // 当 nums[i] <= nums[j] 时： nums[i] 无法接在 nums[j] 之后，
      // 此情况上升子序列不成立，跳过
      if (nums[j] >= nums[i]) continue;
      // nums[i]>nums[j], nums[i] 可以接在 nums[j] 之后（此题要求严格递增），
      // 此情况下最长上升子序列长度为 dp[j] + 1
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    // dp 列表中的最大值即为 全局最长上升子序列的长度
    ans = Math.max(dp[i], ans);
  }
  return ans;
};