c++ dp O(n^2) time solution.


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

Log in to reply
 

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