Leetcode 最长递增子序列

2023-04-27

最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

动态规划解

最优化问题适合用动态规划解。
本题使用dp数组存储以每个元素为结尾的最长递增子序列的长度,其状态转移方程为:
dp[i] = max(dp[j])+1 其中0<j<i && nums[j] < nums[i]
并从前往后填充dp数组。
代码

func lengthOfLIS(nums []int) int {
    dp := make([]int, len(nums))
    for i:= 0; i < len(nums); i++ {
        max := 0
        for j := 0; j < i; j++{
            if dp[j] > max && nums[j] < nums[i] {
                max = dp[j]
            }
        }
        dp[i] = max+1
    }
    result := 0
    for _,v := range dp {
        if v > result {
            result = v
        }
    }
    return result
}
执行用时:52 ms, 在所有 Go 提交中击败了70.79%的用户
内存消耗:3.6 MB, 在所有 Go 提交中击败了64.03%的用户
通过测试用例:54 / 54

评论