Python中最長的遞增序列

如何使用Python中的N平方法和二進位搜索法計算一個數組中最長的遞增子序列。

使用N平方法計算最長的遞增子序列

在Python社區中，有一個著名的問題是關於最長遞增子序列的，在不同的面試中也會被問到。這是一個Leetcode ，問題說：給定一個未排序的整數數組，找出該數組的最長遞增子序列或子集的長度。

一個子集就像一個數組的短數組；每個數組可以有多個子集。另一件事是子數組將是這個[10,9,2,5,3,7,101,18] 數組中的一些元素，但以連續的子序列方式。

它可以像[2, 3, 5, 7] ，但不能像[2,3,101] ，所以在討論子數組時不需要打破順序。而且，在子序列中，元素在數組中出現的順序必須是相同的，但可以是任何一個個體。

例如，在這種情況下，我們可以看到，答案是[2, 3, 7,101] ；5 ，但這是可以的，因為它是一個子序列。

如果我們看到從[10,9,2,5,3,7,101,18] 開始的最長的遞增子序列，我們會發現[2, 5, 7, 101] ；這也可能意味著一個答案，但答案也可能是[2, 3, 7, 101] ，這也是我們的另一個子序列。[3, 7, 101] 也是一個子序列，但這不是最長的，所以我們不考慮它。

可能有不止一個組合；正如我們剛剛看到的，我們只需要返回長度。

通過這個例子，我們可以很容易地想到一個遞歸的解決方案，從零索引開始，沿著所有不同的路徑進行。使用這個數組[0,3,1,6,2,2,7] ，我們可以採取，例如，用0 ，我們可以轉到3 ，或者我們可以轉到1 ，或者轉到6 。

然後，從這一點開始，遞歸地繼續下去。看看下麵的例子，哪條路徑最長，會是指數級的；我們很容易想到必須要有一些動態編程的方法。

所以，我們有一個數組，每個索引至少有一個長度。

[0,3,1,6,2,2,7]
[1,1,1,1,1,1,1]

我們將從第一個索引開始，0 ，其長度是1 ，但有了3 ，我們可以看後面，如果3 大於0 ，那麼3 有2 的長度。如果我們再以1 ，我們將在當前索引之前的所有索引後面尋找。

從零索引中，我們可以看到1 大於0 ，但1 不大於3 ，所以在這一點上，我們要計算0 和1 ，其長度將是2 。

[0,3,1,6,2,2,7]
[1,2,2,1,1,1,1]

在考慮6 ，讓我們從後面開始看，我們知道6 大於[0,1] 或[0,3] ，包括6 ，其長度將是3 ，然後也是2 的長度是3 ，以此類推，這是一個平方的方法。

[0,3,1,6,2,2,7]
[1,2,2,3,3,...]

時間複雜度和空間複雜度

讓我們跳入代碼，創建我們的類，稱為CalculateSubSequence ；在lengthOfLIS 函數裡面，我們初始化我們的nums_list 變數為nums 的長度，這個數組將只有1次。

在嵌套迴圈裡面，我們將檢查該值是否大於我們要檢查的數字。然後，讓我們把我們的nums_list 的i ，我們將更新nums_list 的值，同時使用最大值 nums_list[i].

i 在外迴圈的迭代之後，對於 nums_list[j],j 是在內迴圈迭代後產生的，然後我們將其添加到1 中。最後，我們將返回nums_list 的最大值。

class CalculateSubSequence:
    def lengthOfLIS(self, nums: list[int]) -> int:
        nums_list = [1] * len(nums)
        for i in range(len(nums)-1, -1, -1):
            for j in range(i+1, len(nums)):
                if nums[i] < nums[j]:
                    nums_list[i] = max(nums_list[i], nums_list[j] + 1)
        return max(nums_list)
sbs = CalculateSubSequence()
sbs.lengthOfLIS([0,3,1,6,2,2,7])

這裡的時間複雜度將是n 的平方，而空間複雜度將是o 的n 。

4

上面的解決方案已經足夠了，但是另一種方法，n log ，使用二進位搜索到我們的臨時數組的左邊，使用bisect_left 。

from bisect import bisect_left
#Python小白學習交流群：153708845
class CalculateSubSequence:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n= len(nums)
        tmp=[nums[0]]
        for n in nums:
            x = bisect_left(tmp,n)
            if x ==len(tmp):
                tmp.append(n)
            elif tmp[x]>n:
                tmp[x]=n
        return len(tmp)
sbs = CalculateSubSequence()
sbs.lengthOfLIS([0,3,1,6,2,2,7])

輸出：

4