300_LongestIncreasingSubsequence - a920604a/leetcode GitHub Wiki

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

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