链接:http://codeforces.com/problemset/problem/977/F
题意:首先输入n 然后输入n个数
在这n个数中找出最长的连续的上升的子序列
输出有两行
第一行为最长上升子序列的长度 第二行为序列中各个元素的下标
因为是上升子序列,并且是连续的 所以可以使用map存储一下 map[i] = map[i-1]+1;
这样在我们处理完输入的数据以后便可以用迭代器遍历一下map[i]的最大值 以及i的值(map->second map->first)
i的值便是最长上升子序列的最后一个数的值 map[i]的最大值便是长度 序列开始的第一个值 = i-max(map[i])+1;
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define ll long long 6 #define max3(a,b,c) fmax(a,fmax(b,c)) 7 #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 8 9 bool cmp(const int &a,const int &b) 10 { 11 return a>b; 12 } 13 const int maxn = 2e6+10; 14 15 int main() 16 { 17 map<int,int> m; 18 int n; 19 int a[maxn]; 20 cin >> n; 21 for(int i = 1;i <= n;i++) 22 { 23 scanf("%d",&a[i]); 24 m[a[i]] = m[a[i]-1]+1; 25 } 26 int mmax = -999; 27 int flag = 0; 28 map<int,int>::iterator it; 29 for(it = m.begin();it != m.end();it++) 30 { 31 if(it->second > mmax) 32 { 33 mmax = it->second; 34 flag = it->first; 35 } 36 } 37 flag -= mmax; 38 ++flag; 39 printf("%d ",mmax); 40 for(int i = 1;i <= n;i++) 41 { 42 if(a[i] == flag) 43 { 44 printf("%d ",i); 45 ++flag; 46 } 47 } 48 printf(" "); 49 return 0; 50 }