My 116ms C++ DP solution

  • 0
    class Solution {
        int lengthOfLIS(vector<int>& nums) {
            int n = nums.size();
                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.