requirements

Given an integer array nums, find the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from an array that deletes (or does not delete) the elements of the array without changing the order of the rest of the elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7]. Example 1:

Input: nums = [10,9,2,5,3,7,101,18] output: 4 explanation: the longest increasing subsequence is [2,3,7,101], so length is 4.Copy the code

Example 2:

Input: nums = [0,1,0,3, 3] Output: 4Copy the code

Example 3:

Input: nums = [7,7,7,7,7] Output: 1Copy the code

Tip:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

 

Advanced:

  • Can you design a solution with O(n2) time?
  • Can you reduce the time complexity of the algorithm down to order n log n?

The core code

class Solution:
    def lengthOfLIS(self, nums: List[int]) - >int:
        if not nums:
            return 0
        dp = [1 for _ in range(len(nums))]
        for i in range(1.len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i],dp[j] + 1)
        return max(dp)
Copy the code

An important issue

Answer:

This is a dynamic programming problem, we prepare a list the length of a storage array, we through the two layers of circulation loop to find corresponding value of the first layer, the second loop we are for the tag, when a value is smaller than the current value of the time, our current tag and a maximum of cycle through comparison, whether the update, a better question.