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

Evelyn

QQ: 1809335179

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

#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;
}

最后

以上就是清脆灯泡为你收集整理的C++ 给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）输出最长子序列的长度及对应的子序列的全部内容，希望文章能够帮你解决C++ 给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）输出最长子序列的长度及对应的子序列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。