c++ solution


  • 0
    B

    This is a O(n log n) solution with explaination

    here is my code of O(n^2)

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n=nums.size();
            if(!n) return 0;
            int result=1;
            vector<int> dp(n,1);
            
            for(int i=1;i<n;i++){
                int temp=0;
                for(int j=0;j<i;j++){
                    if(nums[j]<nums[i]) temp=max(temp,dp[j]);
                }
                dp[i]=temp+1;
                result=max(dp[i],result);
            }
            return result;
        }
    };
    

Log in to reply
 

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