【重点】【DP】300.最长递增子序列

Allenlzcoder

已于 2025-03-10 23:50:13 修改

阅读量408

点赞数 9

分类专栏：力扣Top100 文章标签： dp 最长递增子序列

于 2023-12-20 13:50:43 首次发布

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/135106224

版权

力扣Top100 专栏收录该内容

100 篇文章

订阅专栏

本文介绍了两种求解最长递增子序列的方法：一种是利用动态规划（O(N^2)+O(N)），展示了Solution类中的lengthOfLIS方法；另一种是结合二分搜索的耐心排序（O(NlgN)+O(N)），详述了《算法小抄》中相关内容。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

Python

法1：动态规划

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        max_len = 1
        for i in range(1, n):
            for j in range(0, i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
                    max_len = max(max_len, dp[i])

        return max_len

Java

法1：DP

必须掌握，O(N^2) + O(N)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < nums.length; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = res > dp[i] ? res : dp[i];
        }

        return res;
    }
}