最长递增子序列
给你一个整数数组 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