7-5 最长连续递增子序列 (20 分)
给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。
输入格式:
输入第1行给出正整数();第2行给出个整数,其间以空格分隔。
输出格式:
在一行中输出第一次出现的最长连续递增子序列,数字之间用空格分隔,序列结尾不能有多余空格。
输入样例:
15 1 9 2 5 7 3 4 6 8 0 11 15 17 17 10
输出样例:
3 4 6 8
#include <iostream> #include<bits/stdc++.h> using namespace std; int a[1999999]= {0}; int main() { int n; cin>>n; for(int i=1; i<=n; i++) { cin>>a[i]; } int ss= 0 ; int ant = 0; vector<int>ans,ans1; for(int i=1; i<=n-1; i++) { if(a[i+1]>a[i]) { ant++; ans.push_back(a[i]); } else { ant++; ans.push_back(a[i]); if(ant>ss) { ss = ant; ans1 = ans; } ant = 0; ans.clear(); } if(ant>ss) { ss = ant; ans1 = ans; } } if(a[n]>a[n-1]) { ant++; ans.push_back(a[n]); } if(ant>ss) { ss = ant; ans1 = ans; } int top = 1; for(int p:ans1) { if(top)top =0 ; else printf(" "); printf("%d",p); } return 0; }