C++ O(nlogn) solution


  • 0
    X
    class Solution {
    public:
        //[value, maximum_length]
        int bst(vector<int>&v,int&val,int&max_len){
            int right = max_len-1; 
            int left = 0; 
            while(right>=left){
                int mid = (right+left)/2; 
                if(v[mid] == val)
                    return mid-1;
                if(v[mid]>val)
                    right = mid-1; 
                else
                    left = mid+1;
            }
            return right; 
        }
        int lengthOfLIS(vector<int>& nums) {
            if(nums.empty())
                return 0; 
            int max_len = 1; 
            vector<int> record(nums.size(),-1); 
            record[0] = nums[0]; 
            for(int i = 1; i < nums.size(); i++){
                int ind = bst(record,nums[i],max_len); 
                if(ind+2 > max_len)
                    max_len = ind+2; 
                record[ind+1] = nums[i]; 
            }
            return max_len; 
        }
    };
    

    The idea is to use an array "record" to update the minimum of the maximum of all increasing subsequences of size i.
    e.g. nums = [3,8,4,6,5,7]; record = [3,4,6] at iteration i = 3. Thus on iteration 4, the incoming value nums[4] = 5. Bs on record returns index = 1. We then update record[index+1] to 5.
    The update can be done using bs in O(logn), and hence it's an NlogN algorithm in total


Log in to reply
 

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