经典指数          
原因
3058
浏览数
0
收藏数
 

给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱) 例如:给定一个长度为8的数组A{1,3,5,2,4,6,7,8},则其最长的单调递增子序列为{1,2,4,6,7,8},长度为6. 输入描述: 第一行包含一个整数T,代表测试数据组数。 对于每组测试数据: N-数组的长度 a1 a2 ... an (需要计算的数组) 保证: 1 输出描述: 对于每组数据,输出一个整数,代表最长递增子序列的长度。 输入例子: 2 7 89 256 78 1 46 78 8 5 6 4 8 2 17 输出例子: 3 3

     举报   纠错  
 
切换
1 个答案
#include #include"vector" using namespace std; int main() { vectorresult; vectorresult1; vectornum; int T; cin >> T; while (T--) { int a; cin >> a; int n = a; while (a--) { int b; cin >> b; num.push_back(b); result.push_back(1); } for (int i = 0; i < n; i++) { result[i] = 1; for (int j = i - 1; j >= 0; j--) { if (num[i]>num[j] && result[i] < (result[j] + 1)) result[i] = result[j] + 1; } } int max = -1; for (int i = 0; i < n; i++) { if (result[i]>max) { max = result[i]; } } result.clear(); num.clear(); result1.push_back(max); } for (int i = 0; i < result1.size(); i++) { cout << result1[i] << endl; } }
 
切换
撰写答案
扫描后移动端查看本题