LC 300. Longest Increasing Subsequence (LIS)

Link

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