DP + BinarySearch, clean C++ code beating 96% others


  • 1
    S
    int lengthOfLIS(vector<int>& nums) {
            const int len = nums.size();
            if(len <= 1)  return len;
            int c[len+1],ret = 1;
            for(int i = 0; i <= len; i++){
                 c[i] = 0;
            }
            c[1] = nums[0];
            for(int i = 1; i < len; i++){
                int temp = biSearch(c,ret,nums[i]);
                c[temp] = nums[i];
                if(ret < temp)  ret = temp;
            }
            return ret;
        }
        
        int biSearch(int c[], int n, int target){  // to find the right bound
            int left = 1, right = n;
            while(left <= right){
                int mid = (left + right)/2;
                if(c[mid] > target)
                    right = mid - 1;
                else if(c[mid] < target)
                    left = mid + 1;
                else 
                    return mid;
            }
            return left;
        }

Log in to reply
 

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