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/