url

DP

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        vector<int> dp(nums.size());
        int ans=1;
        dp[0]=1;
        for(int i=1;i<nums.size();++i) {
            dp[i]=1;
            for(int j=0;j<i;++j) {
                if(nums[i]>nums[j])
                    dp[i]=max(dp[i],dp[j]+1);
            }
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};

DP 贪心 二分查找

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 1, n = nums.size();
        if(n == 0)  return 0;
        vector<int> d(n + 1, 0);
        d[len] = nums[0];
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] > d[len])    d[++len] = nums[i];
            else{
                int l = 1, r = len;
                while(l <= r){
                    int mid = (l + r) / 2;
                    if(d[mid] < nums[i])    l = mid + 1;
                    else    r = mid - 1;
                }
                d[l] = nums[i];
            }
        } 
        return len;
    }
};