image.png

問題描述

給定一個未排序的整數(shù)數(shù)組，找出最長的遞增子序列。

栗子：

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

解釋：
最長的遞增子序列為：[2,3,7,101]，長度為 4.

注意：

• 可能存在多種最長遞增子序列的組合，只需要返回其長度即可。
• 算法時間復(fù)雜度需要在 O(n2) 之內(nèi)。

想看英文原文的戳這里。

解題思路

從上面的栗子，我們可以看出，遞增子序列不要求連續(xù)。

開門見山，直接說下這道題的解法，即動態(tài)規(guī)劃。使用動態(tài)規(guī)劃的思想，在已有結(jié)果基礎(chǔ)上，計算當前結(jié)果。

拿上述栗子舉例，[10,9,2,5,3,7,101,18]，我們從后往前逐個分析。

為什么要從后往前呢？因為對于我來說這樣看起來更直觀。當然從前往后也是可行的，當你理解了思想后，可以嘗試著從前往后再推導(dǎo)一遍。只不過有些許差別。

從后往前，記錄的是以這個數(shù)開始的遞增子序列的長度。
從前往后，記錄的是以這個數(shù)結(jié)束的遞增子序列的長度。

弄清楚上述差別后，再加上下面的逐步推導(dǎo)說明，相信如何從前往后分析你也能弄明白。

將 f(n) 記為從數(shù)字 n 開始的最大遞增子序列長度。

• 18。從它開始的遞增子序列只有它本身，那么 f(18) = 1。
• 101。其后沒有比它大的數(shù)字，那么從它開始的遞增子序列也只有它自己，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。

不知從上面的推導(dǎo)過程中，你有沒有發(fā)現(xiàn)一些規(guī)律？

當計算某個數(shù)字的最長遞增子序列長度時，根據(jù)所有比其大的數(shù)字的結(jié)果，取出最大值，然后再加上它本身長度 1，即可得出結(jié)果。當然，也可能根本沒有比大的數(shù)字，那么結(jié)果就是 1。

所以，解題思路總結(jié)如下：

• 對于某個數(shù)來說，如果其后沒有比其大的數(shù)，那么長度為 1。
• 如果有比它大的數(shù)，那么取所有大于它的數(shù)的結(jié)果最大值，再加 1。用數(shù)學公式表示如下：

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

在上述過程中，我們可以計算出以每個數(shù)字開始的最長遞增子序列長度，那么整體的最長遞增子序列長度也自然很好求出。

下面給出 js 代碼實現(xiàn)，可以對照著看一下。

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;
};