LeetCode 300. Longest Increasing Subsequence

问题描述



给定一个未排序的整数数组，找出最长的递增子序列。



栗子：

输入：[10,9,2,5,3,7,101,18]
输出：4

解释：
最长的递增子序列为：[2,3,7,101]，长度为 4.



注意：

• 可能存在多种最长递增子序列的组合，只需要返回其长度即可。

• 算法时间复杂度需要在 O(n2) 之内。



想看英文原文的戳这里。

解题思路



从上面的栗子，我们可以看出，递增子序列不要求连续。



开门见山，直接说下这道题的解法，即动态规划。使用动态规划的思想，在已有结果基础上，计算当前结果。



拿上述栗子举例，[10,9,2,5,3,7,101,18]，我们从后往前逐个分析。



为什么要从后往前呢？因为对于我来说这样看起来更直观。当然从前往后也是可行的，当你理解了思想后，可以尝试着从前往后再推导一遍。只不过有些许差别。



从后往前，记录的是以这个数开始的递增子序列的长度。

从前往后，记录的是以这个数结束的递增子序列的长度。



弄清楚上述差别后，再加上下面的逐步推导说明，相信你也能弄明白如何从前往后分析。



下面我们对数字逐个进行分析。将 f(n) 记为从数字 n 开始的最大递增子序列长度。



• 18。从它开始的递增子序列只有它本身，那么 f(18) = 1。



• 101。其后没有比它大的数字，那么从它开始的递增子序列也只有它自己，f(101) = 1。



• 7。101 和 18 都比它大，那它跟谁组合在一起更长呢？很简单，只需取 f(101) 和 f(18) 中的最大值，再加上它自身的长度 1，即 f(7) = max(f(101), f(18)) + 1 = 2。



• 3。7、101、18 比它大，同理，取三者中的最大值，再加上它本身，即 f(3) = max(f(7), f(101), f(18)) + 1 = 3。



• 5。7、101、18 比它大，同样需要取三者最大值，f(5) = max(f(7), f(101), f(18)) + 1 = 3。



• 2。5、3、7、101、18 比它大，同样取这几个中的最大值，f(2) = max(f(5), f(3), f(7), f(101), f(18)) + 1 = 4。



• 9。101、18 比它大，f(9) = max(f(101), f(18)) + 1 = 2。



• 10。101、18 比它大，f(10) = max(f(101), f(18)) + 1 = 2。



不知从上面的推导过程中，你有没有发现一些规律？



当计算某个数字的最长递增子序列长度时，根据所有比其大的数字的结果，取出最大值，然后再加上它本身长度 1，即可得出结果。当然，也可能存在根本没有比它大的数字，那么结果就是 1。



所以，解题思路总结如下：

• 对于某个数来说，如果其后没有比其大的数，那么长度为 1。

• 如果有比它大的数，那么取所有大于它的数的结果最大值，再加 1。用数学公式表示如下：

// x/y/z 都大于 n
f(n) = max(f(x), f(y), f(z), ...) + 1



在上述过程中，我们可以计算出以每个数字开始的最长递增子序列长度，那么整体的最长递增子序列长度也自然很好求出。



下面给出 js 代码实现，可以对照着看一下。

var lengthOfLIS = function (nums) {
  if (nums && nums.length > 0) {
    let result = 1;
	
    // 保存已计算的长度
    let lenList = [];
    // 从后往前计算
    let i = nums.length - 1;
    while (i >= 0) {
      // 同样从后往前计算比其大的最长递增序列长度
      let j = nums.length - 1;
      let maxLen = 0;
      while (j > i) {
        if (nums[j] > nums[i]) {
          // 计算 index，最末尾是 0
          const index = nums.length - 1 - j;
          // 计算最大值
          if (index >= 0 && index < lenList.length) {
            maxLen = Math.max(maxLen, lenList[index]);
          }
        }
        j -= 1;
      }
      maxLen += 1;
		
      // 整体最大值
      if (result < maxLen) {
        result = maxLen;
      }
      lenList.push(maxLen);
      i -= 1;
    }
    return result;
  }
  return 0;
};