最长上升子序列(LeetCode-300)

简介: 最长上升子序列(LeetCode-300)

最长上升子序列(LeetCode-300)


题目

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。


子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。


示例 1:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。


示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4


示例 3:

输入:nums = [7,7,7,7,7,7,7]
输出:1


提示:


1 <= nums.length <= 2500

-104 <= nums[i] <= 104

进阶:


你能将算法的时间复杂度降低到 O(n log(n)) 吗?


思路

五部曲


dp[i] 含义


包含下标 i的最长上升子序列

递推公式


寻找从 0 到 i − 1 各个位置的最长上升子序列加一的最大值


在 n u m s [ i ] > n u m s [ j ]的情况下

d p [ i ] = m a x ( d p [ i ] , d p [ j ] + 1 )


数组初始化


每一个最长上升子序列起始长度至少为1

遍历顺序


从前往后

测试用例



代码展示

class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> dp(n, 1);
        int result = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] > nums[j])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            result = max(dp[i], result);
        }
        return result;
    }
};
目录
相关文章
|
8月前
|
数据采集 运维 数据可视化
阿里云多模态数据信息提取解决方案深度评测与优化建议
本文基于多模态数据信息提取方案的部署体验,深入剖析其在操作界面、部署文档、函数模板、官方示例及实用性与移植性等方面的表现,并提出针对性改进建议。优化建议涵盖模型性能对比、实时校验、故障排查手册、代码注释扩充、行业专属示例集等,旨在提升方案的易用性、功能性和通用性,助力企业在复杂数据处理中高效挖掘价值信息,推动数字化转型。
204 9
|
存储 Java
Dijkstra最短路径(Java)(详细+模板)
Dijkstra最短路径(Java)(详细+模板)
174 4
|
10月前
|
监控 前端开发 JavaScript
前端开发的终极奥义:如何让你的代码既快又美,还不易出错?
【10月更文挑战第31天】前端开发是一个充满挑战与机遇的领域,本文从性能优化、代码美化和错误处理三个方面,探讨了如何提升代码的效率、可读性和健壮性。通过减少DOM操作、懒加载、使用Web Workers等方法提升性能;遵循命名规范、保持一致的缩进与空行、添加注释与文档,让代码更易读;通过输入验证、try-catch捕获异常、日志与监控,增强代码的健壮性。追求代码的“快、美、稳”,是每个前端开发者的目标。
134 3
|
11月前
|
移动开发 小程序 数据可视化
一招学会DIY官网可视化设计支持导出微擎、UNIAPP、H5、微信小程序源码
一招学会DIY官网可视化设计支持导出微擎、UNIAPP、H5、微信小程序源码
228 2
|
机器学习/深度学习 人工智能 并行计算
GPU 和 CPU 处理器的架构
CPU(中央处理器)和 GPU(图形处理单元)是计算机系统中最重要的两种处理器。它们各自的架构设计和技术体系决定了其在不同应用领域中的性能和效率。
537 1
|
安全 Go
Golang深入浅出之-接口(Interfaces)详解:抽象、实现与空接口
【4月更文挑战第22天】Go语言接口提供抽象能力,允许类型在不暴露实现细节的情况下遵循行为约定。接口定义了一组方法签名,类型实现这些方法即实现接口,无需显式声明。接口实现是隐式的,通过确保类型具有接口所需方法来实现。空接口`interface{}`接受所有类型,常用于处理任意类型值。然而,滥用空接口可能丧失类型安全性。理解接口、隐式实现和空接口的使用能帮助编写更健壮的代码。正确使用避免方法,如确保方法签名匹配、检查接口实现和谨慎处理空接口,是关键。
260 1
|
移动开发 JavaScript 前端开发
Web Worker:JavaScript的后台任务解决方案
Web Worker:JavaScript的后台任务解决方案
|
Serverless Python
阿里函数计算中,你可以通过以下步骤在本地安装Python依赖
阿里函数计算中,你可以通过以下步骤在本地安装Python依赖
305 6
|
前端开发 JavaScript 应用服务中间件
个人博客网站如何实现https重定向(301)到http
对于个人网站站注册比较少的,服务器配置不是很好的,没必要https,https跳转到http是要时间的,会影响网站打开的速度。免费的https每年都要更换。
420 2
|
存储 JavaScript
uniapp在不需要后端数据的情况下 怎么记录用户进一次记录一次
uniapp在不需要后端数据的情况下 怎么记录用户进一次记录一次
224 0