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

news/2024/12/5 3:41:50/

❓ 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 – 文件管理 打造「知识循环」体系 官…