Leetcode 300. Longest Increasing Subsequence

Seawolf

1. Given an unsorted array of integers, find the length of longest increasing subsequence.
   
2. 
   
3. Example:
   
4. 
   
5. Input: [10,9,2,5,3,7,101,18]
   
6. Output: 4
   
7. Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
   
8. Note:
   
9. 
   
10. There may be more than one LIS combination, it is only necessary for you to return the length.
    
11. Your algorithm should run in O(n2) complexity.
    
12. Follow up: Could you improve it to O(n log n) time complexity?

复制代码

1. class Solution:
   
2.     def lengthOfLIS(self, nums: List[int]) -> int:
   
3.         if nums == None or len(nums) == 0:
   
4.             return 0
   
5.         dp = [1 for _ in nums]
   
6.         res = 1
   
7.         for i in range(len(nums)):
   
8.             for j in range(i + 1, len(nums)):
   
9.                 if nums[j] > nums[i]:
   
10.                     dp[j] = max(dp[j], dp[i] + 1)
    
11.                 res = max(res, dp[j])
    
12.         return res

复制代码