Simple O(nlogn) solution using lower_bound


  • 0
    D
    class Solution {
        public:
            int lengthOfLIS(vector<int>& nums) {
                vector<int> DP;
                DP.push_back(INT_MIN);
                for(int i=0;i<nums.size();i++)
                {
                    vector<int>::iterator it=lower_bound(DP.begin(),DP.end(),nums[i]);
                    
                    if(it==DP.end())
                    {
                        DP.push_back(nums[i]);
                    }
                    else 
                    {
                        if(*it>nums[i])
                        {
                            *it=nums[i];
                        }
                    }
                }
                return DP.size()-1;
            }
        };

  • 0

    I am not sure what is the behavior here. But if you try this input, you get correct sequence number, but the final entries in DP are wrong. Wondering if it is a coincidence or that is an ok behavior.

    Input:
    [10,22,9,33,21,50,41,60,80]

    DP output:
    -2147483648 9 21 33 41 60 80


Log in to reply
 

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