A C++ O(nlogn) solution with the link to a nice explanation


  • 1
    G
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
       //Here is the explanation of the idea https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf
            // Binary search for the stack where the nums[i] should be pushed, according the tops of the stacks
            // nums[i] cannot be push to any stack whose top is less than nums[i].
            // The number of stacks is the Length of LIS.
    
            int n = nums.size();
            if( n==0 ){
                return 0;
            }
            int end = 0;
            vector<int> tops(n, INT_MIN);
            tops[0] = nums[0];
        
            for(int i=1; i<n; i++){
                int idx = getIndex( tops, end, nums[i] );
                tops[idx] = nums[i];
                end = max( idx, end );
            }
        
            return end+1;
        }
    };
    
    int getIndex( vector<int>& tops, int end, int x ){
        int l = 0;
        int r = end;
    
        while( l<=r ){
            int mid = (l+r)/2;
            if( tops[mid] == x ){
                return mid;
            }
            else if( tops[mid] > x ){
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        return l;
    }

Log in to reply
 

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