給定一個整數序列，計算其中的最長遞增子序列的長度，這是一個典型的動態規劃的算法。
比如8個整數的序列 186 186 150 200 160 130 197 200，最長遞增子序列是 150 160 197 200, 長度為4。
想要解決此問題，可以把這個大問題分解為小問題，依次考慮每個數，計算出包含該數數和該數之前的所有數的最長遞增子序列的長度，計算出的長度值作為該數的對應值記錄下來，最后可以得到這8個數對應的長度值序列，也是8個數，找到這8個數中的最大值就是所有書的最長遞增子序列的長度。
或者也可以這樣想，想要計算8個數的最長遞增子序列的長度有難度，不如先考慮最簡單的情況。只有一個數的時候，最長遞增子序列長度就是1；當有兩個數時，只考慮第一個數和它以前的數的最長遞增子序列就是1，考慮第二個數時只需要找到它之前的所有數中比第二個數小的所有數中最長遞增子序列的長度最大值然后加一 ，就是第二個數的長度。
下面給出實現代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>#include <vector>#include <iterator>using namespace std;int findLoogestIncreaseSeq(vector<int> &vect){ int len = 0; int *count = new int[vect.size()]; for (int i = 0; i < vect.size(); i++) count[i] = 1; for (int i = 0; i < vect.size(); i++) { for (int j = i - 1; j >= 0; j--) { if (vect[j] < vect[i] && count[j] >= count[i]) { count[i] = count[j] + 1; } } if (count[i] > len) len = count[i]; } delete [] count; return len;}int main(){ vector<int> vect; int temp; while (cin >> temp) { vect.push_back(temp); } cout << findLoogestIncreaseSeq(vect) << endl; return 0;} |
補充知識：C++ 求最長遞增子序列（動態規劃）
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| a[i] | 1 | 4 | 7 | 2 | 5 | 8 | 3 | 6 | 9 |
| lis[i] | 1 | 2 | 3 | 2 | 3 | 4 | 3 | 4 | 5 |
時間復雜度為n^2的算法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
//求最長遞增子序列//2019/2/28#include<iostream>using namespace std;int LIS(int a[],int N){ int lis[100] = {}; for(int i =0;i<N;i++)//給每一個數的lis賦初值為1 { lis[i]=1; } for(int i = 1;i<N;i++) { for(int j =0;j<i;j++) { if(a[j]<a[i]&&lis[j]<lis[i]+1) //找出當前元素前面比它小的元素，比較其lis值 lis[i] = lis[j] + 1; } } int max = lis[0]; for(int i =1;i<N;i++) { if(lis[i]>max) max = lis[i]; //找出lis數組中最大值，即最長有序子序列的長度 } return max;}int main(){ int N; int a[100]; while(cin>>N) { for(int i = 0;i<N;i++) cin>>a[i]; cout<<LIS(a,N)<<endl; } return 0;} |
以上這篇C++計算整數序列的最長遞增子序列的長度操作就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/na_beginning/article/details/53611008
