(动态规划) 673. 最长递增子序列的个数 ——【Leetcode每日一题】

news/2024/2/28 18:48:46

❓ 673. 最长递增子序列的个数

难度:中等

给定一个未排序的整数数组 nums , 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。

提示:

  • 1 < = n u m s . l e n g t h < = 2000 1 <= nums.length <= 2000 1<=nums.length<=2000
  • − 1 0 6 < = n u m s [ i ] < = 1 0 6 -10^6 <= nums[i] <= 10^6 106<=nums[i]<=106

💡思路:动态规划

定义 dp 数组,dp[i] 表示 nums 中前 i(包括 nums[i] )最长递增子序列的长度;

并定义 count 数组,表示以 nums[i] 为结尾的字符串,最长递增子序列的个数为 count[i]

  • 遍历 nums 数组,当遍历 nums[i] 时,将nums[i][0, i - 1] 中的数进行比较,当 nums[i] > nums[j]时:

    • 如果 dp[j] + 1 > dp[i],说明找到了一个更长的递增子序列,则更新 dp[i] = dp[j] + 1 ,此时以 j 为结尾的子串的最长递增子序列的个数,就是最新的以 i 为结尾的子串的最长递增子序列的个数,即:count[i] = count[j]
    • dp[j] + 1 == dp[i],说明找到了两个相同长度的递增子序列,那么以 i 为结尾的子串的最长递增子序列的个数 就应该加上以 j 为结尾的子串的最长递增子序列的个数,即:count[i] += count[j]
  • 题目要求最长递增序列的长度的个数,我们定义一个变量 maxCount 把最长长度记录下来;

  • 最后统计所有等于 maxCount长度的 数量。

🍁代码:(C++、Java)

C++

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();int n = nums.size();vector<int> dp(n, 1); //i之前(包括i)最长递增子序列的长度vector<int> count(n, 1); //以nums[i]为结尾的字符串,最长递增子序列的个数int maxCount = 0;for(int i = 0; i < n; i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j]){if(dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1;count[i] = count[j];}else if(dp[j] + 1 == dp[i]) count[i]+= count[j];}if (dp[i] > maxCount) maxCount = dp[i];}}int result = 0;for (int i = 0; i < n; i++) {if (maxCount == dp[i]) result += count[i];}return result;}
};

Java

class Solution {public int findNumberOfLIS(int[] nums) {int n = nums.length;if(n <= 1) return n;int dp[] = new int[n]; //i之前(包括i)最长递增子序列的长度Arrays.fill(dp, 1);int count[] = new int[n]; //以nums[i]为结尾的字符串,最长递增子序列的个数Arrays.fill(count, 1);int maxCount = 0;for(int i = 0; i < n; i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j]){if(dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1;count[i] = count[j];}else if(dp[j] + 1 == dp[i]) count[i]+= count[j];}if (dp[i] > maxCount) maxCount = dp[i];}}int result = 0;for (int i = 0; i < n; i++) {if (maxCount == dp[i]) result += count[i];}return result;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2),其中 n 为数组 nums的长度。
  • 空间复杂度 O ( n ) O(n) O(n)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/670291.html

相关文章

基于Python热门旅游景点数据分析系统设计与实现

博主介绍&#xff1a; ✌全网粉丝30W,csdn特邀作者、博客专家、CSDN新星计划导师、java优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战 ✌ &#x1f345; 文末获取源码联系 &#x1f345; &#x1f447;&#x1f3fb; 精彩专…

计算机软件介绍

计算机软件是指计算机系统中的程序及其文档。程序是计算机任务的处理对象和处理规则的描述&#xff1b;文档是为了便于了解程序所需的阐明型资料&#xff0c;程序必须装入计算机内部才能工作&#xff0c;文档一般是给人看的比一定装入机器。电脑软件一般可分为应用软件和系统软…

电脑编程软件都有哪些

大家好&#xff0c;我是时间财富网智能客服时间君&#xff0c;上述问题将由我为大家进行解答。 电脑编程软件主要有&#xff1a;BASIC、PASCAL、C、COBOL、FORTRAN、LOGO以及VC、VB java等。具体来说&#xff1a; 1、CC 常用软件是MS VC(6.0和更高版本)集成在微软的开发工具v…

六款堪称神器的电脑软件

一&#xff0c;Smallpdf&#xff0c;不是软件&#xff0c;是一个在线网站&#xff0c;针对PDF文件的各种处理方案&#xff0c;可以在线将pdf转换为EXCEL,WORD,JPG,PPT,可以将PPT,JPG,WORD,EXCEL可以转换成pdf&#xff0c;可以将pdf合并&#xff0c;压缩&#xff0c;分割&#x…

10款堪称神器的免费电脑软件推荐

电脑软件有很多&#xff0c;但是免费又好用的软件并不多。下面小编就和大家推荐10款堪称神器的免费电脑软件&#xff0c;每一个都值得收藏&#xff01; 1.DropIt-文件/文件夹自动归类效率工具 DropIt是一款完全免费开源软件的文件/文件夹自动归类效率工具。当我们有较多文件需…

盘点5款超棒的电脑软件

1.Advanced Renamer Advanced Renamer是一款修改文件名称的软件&#xff0c;主要的功能就是帮助用户修改文件名称&#xff0c;并且可以对文件的名称以及扩展名进行修改操作&#xff0c;很多时候我们在使用电脑时会需要用到对文件重命名的操作&#xff0c;这样的话使用这款软件…

分享5款超级实用的电脑软件

1.Alfred 关于快速启动应用程序和打开文件&#xff0c;windows端有Listary和Everything&#xff0c;Mac端的Alfred可以很好的胜任&#xff01; 2.Note it 打开 Note-It&#xff0c;你会发现 Nore-it 就像是贴在屏幕上的便利贴&#xff0c;你可以可以直接在上面输入需要记下…

好用的计算机软件

1. Tabby – 终端神器 Tabby是一款可无限定制的跨平台终端应用程序&#xff0c;用于本地shell、SSH连接。 官网&#xff1a;https://tabby.sh/ github 下载地址&#xff1a; https://github.com/Eugeny/tabby/releases 2. Obsidian – 文件管理 打造「知识循环」体系 官…

推荐4款非常实用的电脑软件

你是否曾经在使用电脑的过程中遇到过各种各样的问题&#xff1f;本文将为您推荐4款小众但非常实用的软件&#xff0c;或许能帮助您解决这些问题。 1.格式工厂 格式工厂是一款功能全面的格式转换软件&#xff0c;支持转换几乎所有主流的多媒体文件格式&#xff0c;包括视频 &a…

5款常用的电脑软件

1.印象笔记 可以编辑笔记&#xff0c;记录灵感、编辑读书笔记、工作笔记等&#xff0c;内容非常丰富&#xff0c;手机与电脑可以同步&#xff0c;而且还支持办公协同&#xff0c;可以将任务进行协同和分类&#xff0c;重要的是如果同事没有做完任务是没有办法删除的&#xff0…

docker学习(一)docker概述

Docker 是什么 Docker 是一个开源的应用容器引擎&#xff0c;基于 Go 语言&#xff0c;并遵从 Apache2.0 协议开源。它可以让开发者打包应用以及依赖包到一个轻量级、可移植的容器中&#xff0c;然后发布到任何流行的 Linux 机器上&#xff0c;也可以实现虚拟化。Docker 可用于…

器件手册识读之 :三极管

器件手册识读之 &#xff1a;三极管 以MMBT3904为例来探讨下三极管的手册信息 一、描述 NPN型通用放大器 二、封装 同一个型号的三极管&#xff0c;可能有不同的封装。 三、最大额定参数 四、热特性 五、电气特性 六、曲线 静态电流放大倍数和电流Ic的关系 集电极-发…

Selenium同窗口和标签一起工作

目录 窗口和标签页 切换窗口或标签页 创建新窗口(或)新标签页并且切换 关闭窗口或标签页 在会话结束时退出浏览器 窗口管理 获取窗口大小 设置窗口大小 得到窗口的位置 设置窗口位置 最大化窗口 最小化窗口 全屏窗口 屏幕截图 元素屏幕截图 执行脚本 打印页面 …

Zigbee模块(CC2530)详解

Zigbee模块&#xff08;CC2530&#xff09; 0. Zigbee概述1. 常见的Zigbee模块2. CC2530模块3. STM32使用CC2530模块方法代码模板 0. Zigbee概述 Zigbee是一种无线通信协议&#xff0c;专为低功耗、低数据速率的应用而设计。它工作在2.4 GHz频段&#xff0c;常用于家庭自动化、…

Idea新建springboot项目遇到的问题及解决

1.更换阿里云 方法&#xff1a; 找到文件路径&#xff1a;Settings > Build,Execution,Deployment > Build Tools > Maven 如下图&#xff1a; 找到相应的settings文件 如果没有就新建一个同名文件&#xff0c;内容如下&#xff1a; <settings xmlns"h…

iPad上的备忘录内容怎么在手机便签上查看?

​​iPad这个设备很多职场人士工作时候都会用到&#xff0c;它的性能比手机要强&#xff0c;便携性比电脑要好&#xff0c;所以成为了职场人的好帮手。通过便签软件可以在iPad上记录一些备忘事项和计划安排&#xff0c;iPad上的备忘录内容怎么在手机便签上查看&#xff1f; 薛…

苹果将推配件让iPad控制智能家居,会治愈智能中控屏的精神内耗吗

智哪儿不久前做过报道&#xff0c;据IDC发布的《中国智能家居设备市场季度跟踪报告&#xff0c;2022年第二季度》显示&#xff0c;2022年上半年&#xff0c;中国智能家居中控屏市场出货量30万台&#xff0c;同比增长160.7%。预计2022年&#xff0c;智能家居中控屏市场出货量将超…

Android与ios对比之系统架构层

1. 引言 自iPhone在07年初次登台将智能手机直接带向移动互联时代后&#xff0c;一方面智能手机普及率直线上升&#xff0c;另一方面整个市场目前呈现了iPhone与Android手机两强争霸的局面。 iOS是由苹果公司开发的手持设备操作系统。最初是设计给iPhone使用的&#xff0c;后来…

手机操作系统开源软件

http://www.oschina.net/project/tag/218/mobile-os?lang0&os0&sortview&p1 开源手机操作系统 Android 开放手机联盟&#xff08;一个由 30 多家科技公司和手机公司组成的团体&#xff09;已开发出 Android&#xff0c;Android 是第一个完整、开放、免费的手机平台…

升级mac系统正在计算机,苹果电脑系统更新,能用手机 APP 了,但我不建议你升级...

原标题&#xff1a;苹果电脑系统更新&#xff0c;能用手机 APP 了&#xff0c;但我不建议你升级 在经历了长达 5 个多月的迭代后&#xff0c;苹果终于在今天正式推送了全新的电脑系统 macOS 11 Big Sur 。 这次系统更新幅度&#xff0c;可以说是这几年里面最大的&#xff0c;整…
最新文章