資料結構
聯網
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究C++ 中最長遞增子序列的數量
假設我們有一個無序整數陣列。我們必須找到最長遞增子序列的數量，所以如果輸入類似於[1, 3, 5, 4, 7]，則輸出為 2，因為遞增子序列是 [1,3,5,7] 和 [1, 3, 4, 7]
要解決這一點，我們將按照以下步驟進行 −
- n := num 陣列的大小，建立兩個陣列 len 和 cnt 的大小為 n，並用值 1 填充它們。
- lis := 1
- 對於 I 的範圍從 1 到 n
- 對於 j 的範圍從 0 到 i – 1
- 如果 nums[i] > nums[j]，那麼
- 如果 len[j] + 1 > len[i]，則 len[i] := len[j] + 1，cnt[i] := cnt[j]
- 否則，當 len[j] + 1 = len[j] 時，cnt[i] := cnt[i] + cnt[j]
- lis := lis 和 len[j] 的最大值
- 如果 nums[i] > nums[j]，那麼
- 對於 j 的範圍從 0 到 i – 1
- ans := 0
- 對於 i 的範圍從 0 到 n – 1
- 如果 len[i] = lis，則 ans := ans + cnt[j]
- 返回 ans
示例(C++)
讓我們看看以下實現以獲得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector <int> len(n, 1), cnt(n, 1);
int lis = 1;
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
if(len[j] + 1 > len[i]){
len[i] = len[j] + 1;
cnt[i] = cnt[j];
}
else if(len[j] + 1 == len[i]){
cnt[i] += cnt[j];
}
}
lis = max(lis, len[i]);
}
}
int ans = 0;
for(int i = 0; i < n; i++){
if(len[i] == lis)ans += cnt[i];
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,3,5,4,7};
cout << (ob.findNumberOfLIS(v));
}輸入
[1,3,5,4,7]
輸出
2
更新於: 2020-4-29
348 瀏覽
廣告