#300.最长递增子序列

nums[j] < nums[i]

Math.max(...dp)

0 <= j < i

nums[j] < nums[i]

dp[j] + 1

dp[i] = Math.max(dp[i], dp[j] + 1);

const dp = new Array(nums.length).fill(1);

j < i

for (let i = 0; i < nums.length; i++) {
  for (let j = 0; j < i; j++) {
    if (nums[j] < nums[i]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
}

/**
 * @param {number[]} nums
 * @return {number} 最长严格递增子序列的长度
 */
var lengthOfLIS = function (nums) {
  // 空数组没有子序列，长度为 0；也避免对空 dp 求最大值得到 -Infinity
  if (nums.length === 0) return 0;

  // dp[i]：必须以 nums[i] 结尾的最长严格递增子序列长度
  // 每个元素都能单独组成长度为 1 的子序列，因此全部初始化为 1
  const dp = new Array(nums.length).fill(1);

  // 从左到右确定每个结尾的最优长度，保证用到的 dp[j] 已经计算完成
  for (let i = 0; i < nums.length; i++) {
    // 枚举当前元素前面的所有位置，而不只是相邻位置：子序列可以不连续
    // j < i 保证选出的元素保持原数组顺序；i = 0 时内层不执行，dp[0] 保持 1
    for (let j = 0; j < i; j++) {
      // 只有 nums[j] 严格小于 nums[i]，才能把 nums[i] 接在它后面
      // 相等时不能接，例如 [2, 2] 的最长严格递增子序列长度仍是 1
      if (nums[j] < nums[i]) {
        // dp[j] + 1：在以 nums[j] 结尾的最优子序列后接上当前元素
        // 可接的位置 j 可能有多个，取最大值，避免较短候选覆盖已有结果
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    // 内层结束后，dp[i] 已确定；若前面没有更小的元素，它仍为 1
  }

  // 最长子序列不一定以最后一个元素结尾，所以取所有 dp[i] 的最大值
  // 例如 [1, 2, 3, 0] 的 dp 为 [1, 2, 3, 1]，答案是 3，而非最后一项 1
  return Math.max(...dp);
};