LeetCode讲解篇之300. 最长递增子序列
题目描述
题解思路
这题我们可以通过动态规划求解，使用一个数组f，数组f的i号元素表示[0, i]范围内最长递增子序列的长度
状态转移方程：f[i] = max(f[j] + 1)，其中 0 < j < i
题解代码
func lengthOfLIS(nums []int) int {
n := len(nums)
f := make([]int, n)
f[0] = 1
ans := 1
for i := 1; i < n; i++ {
f[i] = 1
for j := 0; j < i; j++ {
if nums[i] > nums[j] {
f[i] = max(f[i], f[j] + 1)
}
}
ans = max(ans, f[i])
}
return ans
}
题目链接
https://leetcode.cn/problems/longest-increasing-subsequence/description/
原文地址：https://blog.csdn.net/qq_67733273/article/details/142741599
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！