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

评论