673最長遞增子序列的個數(shù)

給定一個未排序的整數(shù)數(shù)組 nums ， 返回最長遞增子序列的個數(shù) 。

注意 這個數(shù)列必須是 嚴格 遞增的。

示例 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++代碼

#include<iostream>
#include<vector>
using namespace std;
int findNumberOfLIS(vector<int>& nums) {int ans = 0 ;int n = nums.size();vector<int> dp(n+1,1);vector<int> count(n+1,1); //統(tǒng)計當前dp有幾個來源 int maxsq = 1;if(n==0){return 0;}if(n==1){return 1;}for(int i=0;i<n;i++){count[0] = 1;for(int j = 0;j<=i;j++){//dp[all] 初始化都是1,如果是遞減序列，最長遞增子序列所有位子都是1 if(nums[j]<nums[i]){//nums[j]<nums[i],這個是遞增子串的前提條件 /*計算最長遞增子串的長度*/ if(dp[i] < dp[j]+1) {//1.i>j,但是 j位置到i 位置有一個遞增序列，因此i位置的遞增子序列長度需要+1dp[i]=dp[j]+1; //3.這種情況,只是產(chǎn)生了子序列長度的增加，路數(shù)集成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],這個條件會產(chǎn)生遞增序列// count[i] 記錄了在j之前dp[j]+1長度遞增序列的長度// count[j] 表示到達j位子的最長子序列長度的個數(shù)// 實現(xiàn)的功能就是到達i位置的每一路遞增子序列有多少路 }}}}//遍歷conut 表,判斷條件是 maxsq =dp[i],最大子序列所在位子 for(int k=0;k<n;k++){if(maxsq ==dp[k]){//說明這里有最長序列的位置 ans = ans + count[k];  }} return ans;}int main(){vector<int> nums;std::vector<int> 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);cout<<a<<endl;return 0; 
}