300. 最长上升子序列

时间复杂度为O(n^2)的算法

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
          return 0
        
        dp = [0]*n
        # 初始化条件, 如果只有一个元素, 那么这个dp[0]=1
        dp[0] = 1
        max_lis = 1
        
        for i in range (1,n):
          for j in range(0,i):
            # 对于每一个小于nums[i] >nums[j]
            if(nums[i]>nums[j]):
              dp[i] = max(dp[i],dp[j])
              
          dp[i]+=1
          max_lis = max(max_lis,dp[i])
      
      return ret_lis