【LC.673】最长递增子序列的个数 c++版代码_c++子序列个数

作者：小蓝xlanll | 2024-05-02 01:20:40

踩

c++子序列个数

题目

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

注意这个数列必须是严格递增的
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

思路

题目要求找到最长递增子序列的个数，所以我们需要确定最长递增子序列的最大长度是多少，然后是有多少个。

确定长度比较好实现，就是用动态规划，令dp[i]表示以nums[i]结尾的子序列的最大长度，则dp[i]可以根据 $0 < = j < i$ 的dp值确定，如果nums[i]大于nums[j]，说明nums[i]肯定是可以直接紧跟以nums[j]结尾的子序列后面的，相应的，dp[i]就是max(dp[j]+1,dp[i])
具体更新公式如下
$\ 若 \ 0<=j<i \ 且 \ nums[i]>nums[j]$

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/521527

【LC.673】最长递增子序列的个数 c++版代码_c++子序列个数

目录

题目

思路