IOS 算法(中级篇) ----- 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [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

动态规划处理

从小到大计算 dp数组的值，在计算 dp[i] 之前，我们已经计算出 dp[0…i−1] 的值，则状态转移方程为：
dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]

双循环, 外层循环nums中每一个元素 i
内层循环循环 0 ~ i中, 找到满足正序子数组的最长子序列个数

其实我么只要定义一个容器dp, 用来存放个元素最长子序列个数
当我们循环到一个新的满足条件, 只需找到上一个满足条件的最大值 +1 即可

例如:

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

当循环 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 {
        
        // 定义个容器数组, 用来存放从 0~每一个元素 下的最大正序子序列的元素个数
        var dp = Array(repeating: 1, count: nums.count)
        
        // 循环 nums
        for i in 1..<nums.count {
            
            // 循环 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 算法合集地址