最长上升子序列(一)

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    func LIS ( _ nums: [Int]) -> Int {
        guard !nums.isEmpty else {
            return 0
        }

        // dp[i]表示0-i以第i个元素结尾的序列的最长上升子序列
        var dp: [Int] = Array(repeating: 1, count: nums.count)
        for i in 1 ..< nums.count {
            for j in 0 ..< i {
                if nums[j] < nums[i], dp[i] < dp[j] + 1 { // nums[i]和nums[j]构成上升的子序列且新的HLS大于以i结尾的HLS，即dp[i]，更新值
                    dp[i] = dp[j] + 1
                }
            }
        }
        return dp.sorted(by: { $0 < $1 }).last!
    }
}