(DP+二分查找) leetcode 300. Longest Increasing Subsequence

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n==0)
            return 0;
        
        int b[n+1];   //b[i]: when f value is i, smallest nums value(ending value)
        
        int top=0;    //top一定要初始化 否则会指针溢出
        b[0] = INT_MIN;
        
        //O(n)
        for(int i=0; i<n; i++){
            // b[0]...b[top] find the last value b[j] which is smaller than nums[i]
            int start = 0, stop = top;
            int mid, j;
            //O(logn)
            while(start<= stop){
                mid = (start + stop)/2;
                if(b[mid]<nums[i]){
                    j = mid;  //找到一个 先存下来
                    start = mid+1;    //然后在后面找，因为要找最后一个比nums[i]小的
                }
                else
                    stop = mid-1;
            }
            b[j+1] = nums[i];   //f[i] = j+1
            if(j+1 > top)
                top = j+1;   //更新top
        }
        //b[0]...b[top]
        //b[top] stores the smallest ending value for an increasing sequence with length top
        return top;   //top的长度就是f[i]的值，即LIS
    }
};