300. Longest Increasing Subsequence

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining 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], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

• nˆ2方法

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        '''
        [10,9,2,5,3,7,101,18]
        temp = 2
        ret = 1
        
        5>2, temp =5 ,ret = 2
        7 >5, temp = 7, ret = 3
        101 > 7, temp = 101, ret =4
        '''
        if len(nums) == 1: return 1
        dp = [1] * len(nums)
        
        for i in range(1, len(nums)): # 1..8
            for j in range(0, i): # 0..i
                if nums[j]<nums[i]:
                    dp[i]=max(dp[i], dp[j]+1)
        return max(dp)

遞增子序列，用貪心策略，在排序好的列中，bisect_left保證數據插入後一直是排序好的，而這種將數據成堆排序方法叫耐心排序。

[10,9,2,5,3,7,101,18]
[]
[10]
[9]
[2]
[2, 5]
[2, 3]
[2, 3, 7]
[2, 3, 7, 101]

T:O(nlogn), S:O(n)
class Solution(object):
    def lengthOfLIS(self, nums):
        res = []

        for num in nums:
            print(res)
            if not res or num > res[-1]:
                res.append(num)
            else:
                idx = bisect.bisect_left(res,num)
                res[idx] = num

        return len(res)

ref
yt
lib

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)