最长递增子序列

最长递增子序列的状态如何定义？

• 问题: 求数组中最长严格递增子序列的长度 (300);
• 阶段: 按子序列末端索引划分;
• 状态: dp[i] 为以 nums[i] 结尾的最长递增子序列长度;
• 初值: 每个元素自身构成长度 1, 故 dp 全填 1;
• 答案: max(dp), 不一定是 dp[n-1];

如何写出转移方程？

• 推导: 对每个 0 <= j < i, 若 nums[i] > nums[j], 可以把 nums[i] 续在 dp[j] 之后;
• 方程: dp[i] = max(dp[i], dp[j] + 1), 条件 nums[j] < nums[i];
• 复杂度: 时间 O(n^2), 空间 O(n);

const lengthOfLIS = (nums) => {
  const dp = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  return Math.max(...dp);
};

如何同时统计最长递增子序列的个数？

• 问题: 统计最长递增子序列的方案数 (673);
• 状态: 在 dp[i] 之外再维护 count[i], 表示以 nums[i] 结尾的最长递增子序列个数;
• 转移分三种情况:
  • dp[j] + 1 > dp[i]: 首次得到更长长度, dp[i] = dp[j] + 1, count[i] = count[j];
  • dp[j] + 1 === dp[i]: 长度相同, 方案累加 count[i] += count[j];
  • dp[j] + 1 < dp[i]: 不更新;
• 初值: dp 全 1, count 全 1;
• 答案: 先取 max = max(dp), 再把所有 dp[i] === max 的 count[i] 相加;

const findNumberOfLIS = (nums) => {
  const dp = new Array(nums.length).fill(1);
  const count = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] <= nums[j]) continue;
      if (dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
        count[i] = count[j];
      } else if (dp[j] + 1 === dp[i]) {
        count[i] += count[j];
      }
    }
  }
  const max = Math.max(...dp);
  return dp.reduce((sum, len, i) => (len === max ? sum + count[i] : sum), 0);
};

俄罗斯套娃信封问题怎么转化为最长递增子序列？

• 问题: 信封有宽高, 宽高都严格更小时才能套入, 求最多层数 (354);
• 排序: 宽度升序; 宽度相同时高度降序;
• 原因: 同宽信封不能互相套入, 高度降序保证同宽内不会形成递增关系, 从而只按高度取递增即可;
• 转化: 对排序后的高度序列求最长递增子序列;
• 注意: 直接套 O(n^2) 会超时, 需要二分贪心的 O(n log n) 写法;

为什么贪心加二分可以把复杂度降到 O(n log n)？

• 维护: 数组 tails, tails[k] 为长度 k+1 的递增子序列的最小结尾值;
• 贪心: 结尾越小, 后续越容易延长, 所以只保留每种长度的最小结尾;
• 二分: 新元素 x 大于 tails 末尾就追加; 否则找到第一个大于等于 x 的位置并替换它;
• 结果: tails.length 就是最长递增子序列长度;
• 代价: 只得到长度, 无法还原具体子序列;

const lengthOfLISFast = (nums) => {
  const tails = [];
  for (const x of nums) {
    let left = 0;
    let right = tails.length;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (tails[mid] < x) left = mid + 1;
      else right = mid;
    }
    tails[left] = x;
  }
  return tails.length;
};