微博分享的网站怎么做,优化网站排名怎么样,vi设计要素,什么网站专做衣服673最长递增子序列的个数
给定一个未排序的整数数组 nums #xff0c; 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 1: 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列#xff0c;分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 示例 2: 输入: …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 nums.length 2000 -106 nums[i] 106
C代码
#includeiostream
#includevector
using namespace std;
int findNumberOfLIS(vectorint nums) {int ans 0 ;int n nums.size();vectorint dp(n1,1);vectorint count(n1,1); //统计当前dp有几个来源 int maxsq 1;if(n0){return 0;}if(n1){return 1;}for(int i0;in;i){count[0] 1;for(int j 0;ji;j){//dp[all] 初始化都是1,如果是递减序列最长递增子序列所有位子都是1 if(nums[j]nums[i]){//nums[j]nums[i],这个是递增子串的前提条件 /*计算最长递增子串的长度*/ if(dp[i] dp[j]1) {//1.ij,但是 j位置到i 位置有一个递增序列因此i位置的递增子序列长度需要1dp[i]dp[j]1; //3.这种情况,只是产生了子序列长度的增加路数集成j位子的就可以了count[i] count[j];//写一个跟屁虫用于跟踪最长子序列长度最大的是谁if(dp[i]maxsq){maxsq dp[i];} }else if(dp[i] dp[j]1){//2.说明在j位置之前有一x个到i长度为dp[j]1递增序列了//因此说明还有一个相同长度的递增子序列长度count[i]count[i] count[j];//nums[j]nums[i],这个条件会产生递增序列// count[i] 记录了在j之前dp[j]1长度递增序列的长度// count[j] 表示到达j位子的最长子序列长度的个数// 实现的功能就是到达i位置的每一路递增子序列有多少路 }}}}//遍历conut 表,判断条件是 maxsq dp[i],最大子序列所在位子 for(int k0;kn;k){if(maxsq dp[k]){//说明这里有最长序列的位置 ans ans count[k]; }} return ans;}int main(){vectorint nums;std::vectorint dnums;int arr[] {2,2,2,2,2};int arrSize sizeof(arr) / sizeof(arr[0]);for (int i 0; i arrSize; i) {dnums.push_back(arr[i]);}int a findNumberOfLIS(dnums);coutaendl;return 0;
}
