300. Longest Increasing Subsequence

發表於 | 分類於

problem

給定一個整數陣列，找出最遞增子序列。

solution

option 1 - dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1);
        //  10  9   2   5   3   7   101 18
        //  1   1   1   1   1   1   1   1
        //  1   1   1   2   2   3   4   4
        
        int ret = 1;
        for(int i=1;i<n;++i){
            // 每次確定第 ith 最長子序列
            for(int j=0;j<i;++j){
                if(nums[i] > nums[j] ) dp[i] = max(dp[i], dp[j]+1);
            }
            ret = max(ret,dp[i]);
        }
        return ret;
    }
};

更多可以參考patience sorting

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
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int piles = 0, n=nums.size();
        vector<int> top(n,0);
        for(int i=0;i<n ; ++i){
            int poker = nums[i];
            int l =0, r = piles;
            // 從top 陣列可視範圍 l-r 區間找到poker放入的位置，使得top 是單調遞增陣列
            
            while(l<r){
                int mid = l + (r-l)/2;
                if(top[mid] == poker) r = mid;
                else if(top[mid] < poker ) l = mid+1;
                else r = mid;
                
            }
            // 插入的位置不在陣列可視範圍內
            if(l==piles) piles++;
            // 將poker 放進陣列top
            top[l] = poker;
            
            //  2   3   7   18 
            //  9   5   101
            //  10
            
        }
        return piles;
    }
};

analysis

  • option 1 - dp
    • time complexity O(n^2)
    • space complexity O(1)
  • option 2 - binary search
    • time complexity O(nlogn)
    • sapcency complexity O(1)