300. Longest Increasing Subsequence

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Array、Binary Search、Dynamic Programming

一、題目

Given an integer array nums, return the length of the longest strictly increasing subsequence

Example 1:

  • Input: nums = [10,9,2,5,3,7,101,18]
  • Output: 4
  • Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

  • Input: nums = [0,1,0,3,2,3]
  • Output: 4

Example 3:

  • Input: nums = [7,7,7,7,7,7,7]
  • Output: 1

Constraints:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log n) time complexity

二、分析

  • 不定序列型的動態規劃問題。或我習慣稱作 LIS 型或俄羅斯娃娃型
    • 定義 dp[i]：第 i 個元素的最長遞增子序列為多少。
    • 故只要從第 i 個元素往前找到比 nums[i] 還大，同時又擁有最長遞增子序列的元素，再加 1 即可。
      • dp[i] = max(dp[i], dp[j] + 1)
    • 最終的結果是 max({dp[i]})。

三、解題

1. DP

  • Time complexity: \(O(n^2)\)
  • Space complexity: \(O(n)\)
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int res = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
                res = max(res, dp[i]);
            }
        }
    }
    return res;
}

2. DP + Binary Search

  • Time complexity: \(O(n\log n)\)
  • Space complexity: \(O(n)\)
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, INT_MAX);     // dp[n] 裝的是實際排出來的數字，沒排到的位置以 INT_MAX 填滿，以使用 binary search
    int res = 0;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(dp.begin(), dp.end(), nums[i]);
        *it = min(*it, nums[i]);    // 用 greedy 的想法，同樣位子上，數字愈小，愈有可能形成最長遞增子序列
        res = max(res, (int)(it - dp.begin())+1);
    }
    return res;
}

回目錄 Catalog