文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書

1. Description

Longest Increasing Subsequence

2. Solution

解析：Version 1，最長遞增子序列，典型的動態(tài)規(guī)劃問題，定義狀態(tài)：以nums[i]作為結(jié)尾元素的最長遞增子序列的長度，狀態(tài)轉(zhuǎn)移方程：遍歷nums[i]之前的元素nums[j]，如果nums[i] > nums[j]，則其最長遞增子序列的長度為max(dp[i], dp[j] + 1)，遍歷之后，可以找到以nums[i]作為結(jié)尾元素的最長遞增子序列長度，最終返回的是所有元素的最長遞增子序列長度中最長的一個。Version 2是一種技巧，使用order作為有序序列保持最長遞增子序列長度，當新元素比有序序列的最后一個元素大時，此時增加新元素到有序序列中，否則，則將新元素插入到當前序列中，替換比其大或相等的元素，保證左側(cè)元素都比它小，此時長度不變，order中始終保留較小的元素，這樣利于插入新元素。order的長度等于最長遞增子序列長度，但order的數(shù)據(jù)不一定等于最長遞增子序列的數(shù)據(jù)。

• Version 1

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

• Version 2

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        order = []
        for i in range(n):
            if len(order) == 0 or order[-1] < nums[i]:
                order.append(nums[i])
            else:
                index = bisect.bisect_left(order, nums[i])
                order[index] = nums[i]
        return len(order)

Reference

1. https://leetcode.com/problems/longest-increasing-subsequence/