Using binary search to find insert position and updating the maxlen (c++ nlogn)


  • 0
    G
    int insertPos(vector<int> &lis,int len,int val)
        {
            int start=0,end=len,mid;
            while(start<end)
            {
                mid = (start+end)/2;
                if(lis[mid]>val) end=mid;
                else if(lis[mid]<val) start=mid+1;
                else return mid;
            }
            if(lis[start]<val) return start+1;
            else return start;
        }
        int lengthOfLIS(vector<int>& nums) {
            int n=nums.size(),len,pos,i;
            if(n<=1) return n;
            vector<int> lis(n);
            lis[0]=nums[0],len=0;
            for(i=1;i<n;i++)
            {
                pos=insertPos(lis,len,nums[i]);
                lis[pos]=nums[i];
                len = max(len,pos);
            }
            return len+1;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.