C++ Solution with two different versions: DP with O(n^2) time and BinearySearch with O(nlgn) time


  • 2
    Y
    /*
    * DP, O(n^2) Time & O(n) Space
    */
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int ans = 1;
            if(nums.size() < 2)
                return nums.size();
            vector<int> dp(nums.size() + 1);
            for(int i = 0; i < nums.size(); ++ i)
                dp[i] = 1;
            for(int i = 1; i < nums.size(); ++ i){
                for(int j = 0; j < i; ++ j){
                    if(nums[i] > nums[j])
                        dp[i] = max(dp[i], dp[j] + 1);
                }
                ans = max(ans, dp[i]);
            }
            return ans;
        }
    };
    
    /*
    * Bineary Search, O(nlgn) time and O(n) space
    */
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int ans = 0;
            if(nums.size() < 2)
                return nums.size();
            vector<int> stk(nums.size() + 1);
            for(int i = 0; i < nums.size(); ++ i){
                bsearch(ans, nums[i], stk);
            }
            return ans;
        }
    private:
        void bsearch(int &ans, int val, vector<int> &stk){
            if(ans == 0 || val > stk[ans - 1]){
                stk[ans ++] = val;
                return ;
            }
            if(val <= stk[0]){
                stk[0] = val;
                return ;
            }
            int l = 0, r = ans - 1, id;
            while(l <= r){
                int mid = (l + r)>>1;
                if(stk[mid] == val)
                    return;
                else if(stk[mid] < val){
                    id = mid;
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
            stk[l] = val;
        }
    };

Log in to reply
 

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