1 題目描述

給定一個整數數組nums，找到一個最長的遞增子序列的長度。

2 解法

2.1 Recursion

這題是DP問題，假設我們有一組數字[1, 2, 3, 7, 4, 5, 6] 我們需要比較當前的值 nums[i]是否比上一個值 last還要大，當滿足條件的時候，我們就要思考一個問題到底是**要把當前的值考量進去，還是跳過當前的？**這就會牽涉到兩個公式，類似背包問題，偷與不偷，那這裡就是塞與不塞：

  • 塞： 1塞(當前值) + 未來的最佳解
  • 不塞： 不塞 + 未來的最佳解

以上述的例子來說，如果我們走到 7 的時候，我們可以選擇塞或不塞

  • 如果塞的話，未來的最佳解都是 0，因為沒有比7大的值了
  • 如果不塞的話，後面還有4, 5, 6可以選擇

這樣的話我們可以得出一個公式，假設i是當前的值：

  • 塞： 1 + helper(nums[i+1:])
  • 不塞： helper(nums[i+1:])

但是還有一個問題需要考慮，就是我們在往後比較的時候，需要知道被比較的對象是誰，舉例來說一樣從7開始

  • 塞：那後續與4, 5, 6比較的就是7
  • 不塞：那後續與4比較的就是3，與5比較的就是4以此類推，會隨著i的變化而變化
    而上面這個被後續比較的對象就是last，所以我們的公式就變成：
  • 塞： 1 + helper(nums[i], nums[i+1:])
  • 不塞： helper(last, nums[i+1:])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def lengthOfLIS(self, nums: List[int]) -> int:
    def helper(last, i):
        # 終止條件 走到底了
        if i == len(nums):
            return 0
        # 當前值 e.g. 7 
        cur = nums[i]
        take = 0
        # last=3, cur=7 如果發現可以塞的話，我們就要比較塞與不塞的最大值
        if cur > last:
            # 塞：(計數+1) + 後續的最佳解(此時last變成cur, 與下一個(i+1)比較
            take = 1 + helper(cur, i+1)
        # 不塞：不計數 + 後續的最佳解(此時last不變繼續傳下去比較, 與下一個(i+1)比較)
        not_take = helper(last, i+1)
        # 取最大值：塞與不塞
        return max(take, not_take)

    return helper(float('-inf'), 0)

2.1 Recursion with Memoization

上面的解法是遞迴，但是遞迴的問題就是會有很多重複的計算，所以我們可以用memoization來解決這個問題，這樣就不用重複計算了。我們從上面可以發現i是慢慢增長的，所以我們如果可以儲存不同長度且不同last時的最佳解，那就可以避免重複計算。

我們儲存dp[(last, i)]=max(take, not_take)，這樣就可以知道在不同長度的狀況下，最佳解是多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def lengthOfLIS(self, nums: List[int]) -> int:
    dp = {}  # 使用字典來進行記憶化

    def helper(last, i):
        if i == len(nums):
            return 0
        # 如果這個子問題已經計算過，則直接返回結果
        if (last, i) in dp:
            return dp[(last, i)]
        cur = nums[i]
        if cur > last:
            add = 1 + helper(cur, i + 1)
        else:
            add = 0
        not_add = helper(last, i + 1)
        # 記錄結果
        dp[(last, i)] = max(add, not_add)
        return dp[(last, i)]

    return helper(float('-inf'), 0)

2.2 Iterative + Tabulation

接下來我們需要使用迭代的方式來解決這個問題。這題我是參考Youtube | Neetcode介紹得非常詳細。首先，他是一個拿與不拿的問題，因此我們使用比較簡單的例子[1,2,4,3]先畫個樹狀圖來看一下有哪些狀況，不用全部畫出來，我們就先繪製出第一個到底的狀況就好如下圖：


首先你會發現:

  • LTS[3]因為i=3已經是最底了，基本上從3往後看只會有自己一個長度，因此 LTS[3]=1是無庸置疑的。
  • LTS[2]因為i=2，所以有兩種可能max(1, 1+LTS[3])但是1+LTS[3]只有在nums[2]>nums[3]的情況下才會成立，所以仍然是LTS[2]=1
  • LST[1]因為i=1後面有三種可能max(1, 1+LTS[2], 1+LTS[3])就有點像是max(自己, 自己+id2, 自己+id3)，而i=2因為比後面的數字都還要小，所以自己+id2或自己+id3都成立。因此我們會得到max(1, 1+1, 1+1)=2
  • LST[0]因為i=0後面有四種狀況max(1, 1+LTS[1], 1+LTS[2], 1+LTS[3])，而i=1因為比後面的數字都還要小，所以自己+id1或自己+id2或自己+id3都成立。因此我們會得到max(1, 1+2, 1+1, 1+1)=3

如果你繼續嘗試把其他可能都畫出來，你會發現都已經是重複的狀況：

從前述講的順序中，我們會發現可以從後面往前面推，然後使用雙層for迴圈，並且時間複雜度是O(n^2)。
最外層i是從n-1到0，內層j是從i+1到n，這樣就可以得到所有的狀況，並且可以得到最佳解。

最後程式碼如下，就解出來了：

1
2
3
4
5
6
7
dp = [1]*len(nums) # 至少可以包含自己，一定會有最小值1
for i in range(n-1, -1, -1):
    for j in range(i+1, n):
        # 只有在nums[i] < nums[j]的情況下才會更新否則都是自己
        if nums[i] < nums[j]:
            dp[i] = max(dp[i], 1+dp[j])
return max(dp)

時間複雜度：O(n^2)
空間複雜度：O(n)

2.3 O(NlogN) Patience Sort

接下來題目要求試試看O(NlogN)其實就要使用Binary Search，但是在使用Binary Search之前，我們需要先了解一下一個超級神奇的演算法！叫做Patience Sort，他是一個卡牌遊戲，可以幫助我們找到最長的遞增子序列。我們先來介紹卡牌遊戲的規則：

首先，我們有一組卡牌，規則是：

  • 如果當前的卡牌比piles的最後一張卡牌還要大，那就直接放到最後一張卡牌的後面
  • 如果當前的卡牌比piles的最後一張卡牌還要小，那就要找到一張比當前卡牌還要大的卡牌，然後放在上面，如果找不到的話，就要開一個新的pile

最後你會發現，每個piles最上面的卡牌由左到右是遞增的

更神奇的事情發生了，這個piles的數量就是最長的遞增子序列的長度！因為每個piles一定可以找到一張牌可以排出遞減的牌組

所以我們用這個卡牌的遊戲規則其實跟我們的地目很像

  1. 有一個無序的卡牌
  2. 然後我們想要知道最長的遞增子序列

如果我們改一下題目的規則：

  1. 如果當前的卡牌比piles的最後一張卡牌還要小，就要覆蓋該piles的最後一張卡牌
  2. 如果當前的卡牌比piles的最後一張還要大，就建立新的piles

來重新看一下題目，這樣我們到時候堆疊出來的piles就會長這樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
nums = [10,9,2,5,3,7,101,18]

dp 就像是紀錄每個 pile 的 top，如果發現新的牌比 top 還要大，就直接放在後面（建立新的pile）
一開始我們就直接把10放進去吧，此時pile的數量是1，而該pile的top是10
len   1
dp = [10]

2----------------------------
10  9  2  5  3  7  101  18
    ^  
現在換考慮 9, 9 比pile的top10還要小 更新pile top為9
len   1
dp = [9]    

3----------------------------
10  9  2  5  3  7  101  18
       ^  
現在換考慮 2, 2 比pile的top10還要小 更新pile top為2
len   1
dp = [2]    

4----------------------------
10  9  2  5  3  7  101  18
          ^  
現在換考慮 5, 因為比pile的top2還要大，所以建立新的pile
len   1  2
dp = [2  5]   

5----------------------------
10  9  2  5  3  7  101  18
             ^  
現在換考慮 3, 因為比pile[2]的top5還要小，更新pile[2]的top為3
len   1  2
dp = [2  3]   

6----------------------------
10  9  2  5  3  7  101  18
                ^  
現在換考慮 7, 因為比任何pile的top還要大，所以建立新的pile
len   1  2  3
dp = [2  3  7]  

7----------------------------
10  9  2  5  3  7  101  18
                    ^  
現在換考慮 101, 因為比任何pile的top還要大，所以建立新的pile
len   1  2  3   4
dp = [2  3  7  101]  

8----------------------------
10  9  2  5  3  7  101  18
                        ^  
現在換考慮 18, 只有pile[4]的top比18還要大，所以更新pile[4]的top為18
len   1  2  3   4
dp = [2  3  7   18] 

最後dp的長度就是最長的遞增子序列

用python來實現如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
"""
Speed: O(n*n)
Space: O(n)
"""
def lengthOfLIS(self, nums: List[int]) -> int:
    dp = [nums[0]]
    for x in nums[1:]:
        if x > dp[-1]:
            dp.append(x)
        else:
            for i in range(len(dp)):
                if dp[i] >= x:
                    dp[i] = x
                    break
    return len(dp)

但是這樣還是O(N^2)因此我們可以用二分查找來解決這個問題，這樣就可以達到O(NlogN)的時間複雜度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def lengthOfLIS(self, nums: List[int]) -> int:
    dp = []
    for x in nums:
        if not dp or x > dp[-1]:
            dp.append(x)
        else:
            # 二分搜尋的演算法 l=left, r=right, mid=middle
            l, r = 0, len(dp)-1
            while l < r:
                mid = l + (r-l)//2
                if dp[mid] < x:
                    # 如果 x 比 dp[mid] 還要小，l 會一直往右移動（變成mid+1）為了不跟 r 重疊，因為r可能是之前的mid
                    l = mid + 1
                else:
                    # 如果 x 比 dp[mid] 還要大，r 會一直往左移動（變成mid）
                    r = mid
            dp[l] = x
    return len(dp)

或是直接使用套件bisect來解決這個問題

1
2
3
4
5
6
7
8
9
10
11
12
import bisect from bisect_left

def lengthOfLIS(self, nums: List[int]) -> int:
    dp = []
    for x in nums:
        i = bisect_left(dp, x)
        if i == len(dp):
            dp.append(x)
        else:
            i = bisect_left(dp, x) # 找到第一個比x大的位置
            dp[i] = x  # 更新
    return len(dp)

3 結論

這題真的是我花了2天慢慢想，完全沒想過Patience Sort這種方式來解題目，太神奇拉！！！超愛這題！