C++ 给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）输出最长子序列的长度及对应的子序列

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
40
41
42
43
44
45
46
47
#include<iostream>
#include <vector>
using namespace std;
int main() {
int T;
cin >> T;
vector<int> num;
vector <int> result;
vector<int> out;
while (T--) {
int N;
cin >> N;
int n = N;
while (n--) {
int b;
cin >> b;
num.push_back(b);
result.push_back(1);
}
int max = 0;
for (int i = 0; i < N; i++) {
for (int j = i - 1; j >= 0; j--) {
if (num[i] > num[j] && result[i] < result[j] + 1) {
/*result[j]里存放的是比当前值小且最多存在的个数,所有后面的值如果比前面的大，
只要比较当前result[i]与result[j]即可，因为j之前的比num[j]小的书已经全部包含在result[j]里了*/
result[i] = result[j] + 1;
}
}
if (result[i] > max)
max = result[i];
}
cout << max << endl;
for (int i = N-1; i >=0; i--)
{
if (result[i] == max){
out.push_back(num[i]);
max--;
}
}
num.clear();
result.clear();
for (int i = out.size()-1; i >=0; i--)
cout << out[i] << " ";
cout.clear();
}
return 0;
}