My 116ms C++ DP solution


  • 0
    T
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n = nums.size();
            if(n<2)
                return n; 
                
            vector<int> DP(n, 1); // dynamic programming
            // DP[i] denotes the length of the longest increasing sequence
            // in nums[0,1,2,i] with nums[i] as the ending element
            int i, j;
            for(i=1; i<n; i++)
            {
                for(j=0; j<i; j++)
                {
                    if(nums[i] > nums[j])
                        DP[i] = max(DP[i], DP[j]+1);
                }
            }
            
            int result=0;
            for(i=0; i<n; i++)
            {
                result = max(result, DP[i]);
            }
            
            return result;
        }
    };

Log in to reply
 

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