題目網址：https://leetcode.cn/problems/longest-increasing-subsequence/

題意：給一整數 array nums, 找出其中最長的嚴格遞增 subarray 之長度。

進階：設計 $O(n \cdot log(n))$ time 的演算法

Solution 1：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態
  • dp[i]：nums[1:i] 中 LIS 的長度

2. 得到轉移方程：

  • dp[i] = max(dp[i], dp[j] + 1), for 1 ≤ j < i

3. 初始化：

  • dp[0]：當沒有元素時, LIS 的長度為 0
  • dp[i]：至少一個元素時, LIS 的長度最小為 1, 其中 1 ≤ i ≤ n
  • res：至少一個元素時, LIS 的長度最小為 1

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        const int n = nums.size();
        
        nums.emplace(nums.begin(), 0);

        int res = 1; // 題目給定 nums 不為空
        vector<int> dp(n + 1, 1);
        dp[0] = 0;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                    res = max(res, dp[i]);
                }
            }
        }
        
        return res;
    }
};
  • time：$O(n^2)$ ➔ for loop
  • space：$O(n)$ ➔ dp

Solution 2：

想法：使用 DP + Greedy + Binary Search, 我們在乎只當前 subarray 的結尾

每當有一新數字 num 進來之後, 判斷 num 是否比現在 dp.back() 的數值大

  • 若 num > dp.back(), 那就直接放到 dp.back() 的後面, 成為新的結尾
  • 否則, 用 Binary Search 找到 dp 中從左數來第一個大於 num 的數字, 並將其替換掉。
    （因為 dp 結尾變小, 將來可能可以接得更長）
    e.g. 下圖中紅框部分, 用 5 取代 8, 使 dp 結尾變小, 讓之後的 6 能加入

e.g. nums = [3, 4, 1, 2, 8, 5, 6]

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        dp.emplace_back(nums[0]);

        for (int i = 1; i < nums.size(); ++i) {
            if (dp.back() < nums[i]) {
                dp.emplace_back(nums[i]);
            } else {
                *lower_bound(dp.begin(), dp.end(), nums[i]) = nums[i];
            }
        }

        return dp.size();
    }
};
  • time：$O(n \cdot log(n))$ ➔ for loop, 其中 lower_bound() 是使用 Binary Search 實作的
  • space：$O(n)$ ➔ dp