题目描述

题解思路

这题我们可以通过动态规划求解，使用一个数组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/