本篇推文共計(jì)2000個(gè)字，閱讀時(shí)間約3分鐘。

題目描述：

給一個(gè)整數(shù)數(shù)組nums，

找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度。

子序列是由數(shù)組派生而來(lái)的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。

例如舉例所示：

輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長(zhǎng)遞增子序列是[2,3,7,101]，因此長(zhǎng)度為4。

輸入：nums = [0,1,0,3,2,3]
解釋：最長(zhǎng)遞增子序列是[0,1,2,3]，因此長(zhǎng)度為4。

由題目描述可知

設(shè)數(shù)組dp[i]的值代表數(shù)組nums

前i個(gè)數(shù)字的最長(zhǎng)遞增子序列長(zhǎng)度

設(shè)j∈[0,i)，每輪計(jì)算新dp[i]時(shí)，

遍歷[0,i)列表區(qū)間，做以下判斷：

1.當(dāng)nums[i]>nums[j]時(shí)：

nums[i]可以接在nums[j]之后（此題要求嚴(yán)格遞增），
此情況下最長(zhǎng)上升子序列長(zhǎng)度為
dp[i]=dp[j]+1；

2.當(dāng)nums[i]<=nums[j]時(shí)：

nums[i]無(wú)法接在nums[j]之后，
此情況上升子序列不成立，跳過(guò)

在情況1中，計(jì)算出dp[j]+1的最大值，即為數(shù)組nums的最長(zhǎng)上升子序列長(zhǎng)度。

具體實(shí)現(xiàn)的辦法可以使用遍歷j時(shí)，每輪執(zhí)行最大值比較公式：

dp[i]=max(dp[i],dp[j]+1)

將遍歷每一輪的最長(zhǎng)上升子序列長(zhǎng)度存入數(shù)組dp[i]中

在初始化時(shí)

將dp[i]所有元素置為1，含義為每個(gè)元素都至少可以單獨(dú)成為子序列，此時(shí)長(zhǎng)度為1

例如此種情況：

nums=[2,2,2,2,2]
則該數(shù)組nums的最長(zhǎng)上升子序列為1

我們用一個(gè)實(shí)際的例子，來(lái)解答此題

首先判斷數(shù)組nums非空，如果是一個(gè)空數(shù)組

則not nums=1

if 1 則返回 0(即不會(huì)執(zhí)行后面代碼操作)

if not nums:
    return 0

接下來(lái)我們用一個(gè)非空數(shù)組nums解釋下面的代碼

設(shè)置nums=[10,12,11,9,15,13,21]

設(shè)置dp=[1,1,1,1,1,1,1]

dp=[1]*len(nums)

如下圖所示即為初始狀態(tài)數(shù)組nums與dp的值

當(dāng)i=0時(shí)，此時(shí)數(shù)組nums[10,12,11,9,15,13,21]中

只有[10]一個(gè)子數(shù)列，

所以此時(shí)最長(zhǎng)上升子序列為[10]

最長(zhǎng)上升子序列長(zhǎng)度dp=1,如下圖紫色區(qū)域標(biāo)出。

當(dāng)i=1時(shí)，此時(shí)數(shù)組nums[10,12,11,9,15,13,21]中

只有[10,12]一個(gè)子數(shù)列，

所以此時(shí)最長(zhǎng)上升子序列為[10,12]

最長(zhǎng)上升子序列長(zhǎng)度dp=2,如下圖紫色區(qū)域標(biāo)出。

當(dāng)i=2時(shí)，此時(shí)數(shù)組nums[10,12,11,9,15,13,21]中

此時(shí)數(shù)列為[10,12,11]，

此時(shí)最長(zhǎng)上升子序列為[10,12]

最長(zhǎng)上升子序列長(zhǎng)度dp=2,如下圖紫色區(qū)域標(biāo)出。

當(dāng)i=3時(shí)，此時(shí)數(shù)組nums[10,12,11,9,15,13,21]中

此時(shí)數(shù)列為[10,12,11,9]，

此時(shí)最長(zhǎng)上升子序列為[10,12]

最長(zhǎng)上升子序列長(zhǎng)度dp=2,如下圖紫色區(qū)域標(biāo)出。

當(dāng)i=4時(shí)，此時(shí)數(shù)組nums[10,12,11,9,15,13,21]中

此時(shí)數(shù)列為[10,12,11,9,15]，

此時(shí)最長(zhǎng)上升子序列為[10,12,15]

最長(zhǎng)上升子序列長(zhǎng)度dp=3,如下圖紫色區(qū)域標(biāo)出。

當(dāng)i=5時(shí)，此時(shí)數(shù)組nums[10,12,11,9,15,13,21]中

此時(shí)數(shù)列為[10,12,11,9,15,13]，

此時(shí)最長(zhǎng)上升子序列為[10,12,15]

最長(zhǎng)上升子序列長(zhǎng)度dp=3,如下圖紫色區(qū)域標(biāo)出。

當(dāng)i=6時(shí)，此時(shí)數(shù)組nums[10,12,11,9,15,13,21]中

此時(shí)數(shù)列為[10,12,11,9,15,13,21]，

此時(shí)最長(zhǎng)上升子序列為[10,12,15,21]

最長(zhǎng)上升子序列長(zhǎng)度dp=4,如上圖紫色區(qū)域標(biāo)出。

最后返回記錄i從0到6的數(shù)組dp[i]最大值即可

return max(dp)

完整代碼如下：

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