給你一個整數(shù)數(shù)組 nums ，找到其中最長嚴格遞增子序列的長度。
子序列是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。

例子

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

輸入：nums = [0,1,0,3,2,3]
輸出：4

解題思路

1.png

2.png

3.png

4.png

5.png

6.png

7.png

動態(tài)規(guī)劃處理

從小到大計算 dp數(shù)組的值，在計算 dp[i] 之前，我們已經計算出 dp[0…i?1] 的值，則狀態(tài)轉移方程為：
dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]

雙循環(huán), 外層循環(huán)nums中每一個元素 i
內層循環(huán)循環(huán) 0 ~ i中, 找到滿足正序子數(shù)組的最長子序列個數(shù)

其實我么只要定義一個容器dp, 用來存放個元素最長子序列個數(shù)
當我們循環(huán)到一個新的滿足條件, 只需找到上一個滿足條件的最大值 +1 即可

例如:

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

當循環(huán) i = 5 當前元素為7時, dp=[1, 1, 1, 2, 2, 1, 1, 1]
j=0 7 < 10 不滿足

j=1 7 < 9 不滿足

j=2 7 > 2 滿足, 2的dp下標(當前最大子序列值)為1,
那么dp[i] = max(dp[i], dp[j]+1) = max(1, 2) = 2

j=3 7 > 5 那么dp[i] = max(dp[i], dp[j]+1) = max(2, 2 + 1) = 3

j=4 7 < 3 那么dp[i] = max(dp[i], dp[j]+1) = max(3, 2 + 1) = 3

后面依次這樣操作

未翻譯版

    func lengthOfLIS(_ nums: [Int]) -> Int {
        
        var dp = Array(repeating: 1, count: nums.count)
        
        for i in 1..<nums.count {
            
            for j in 0..<i {
                
                if nums[i] > nums[j] {
                    dp[i] = max(dp[i], dp[j] + 1)
                }
            }
        }
        
        return dp.max() ?? 1
    }

翻譯版

    func lengthOfLIS(_ nums: [Int]) -> Int {
        
        // 定義個容器數(shù)組, 用來存放從 0~每一個元素 下的最大正序子序列的元素個數(shù)
        var dp = Array(repeating: 1, count: nums.count)
        
        // 循環(huán) nums
        for i in 1..<nums.count {
            
            // 循環(huán) 0~i 中元素
            for j in 0..<i {
                
                // 如果存在當前元素大于之前元素, 情況取 dp[i] 與 dp[j]+1 的最大值
                if nums[i] > nums[j] {
                    // dp取 當前i的dp[i]與dp[j]+1 兩者的最大值
                    dp[i] = max(dp[i], dp[j] + 1)
                }
            }
        }

        // 最后取dp的最大值即可        
        return dp.max() ?? 1
    }

題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址