描述
You are given an integer array of length nn.
You have to choose some subsequence of this array of maximum length
such that this subsequence forms a increasing sequence of consecutive
integers. In other words the required sequence should be equal to
x,x+1,…,x+k−1 for some value xx and length kk.Subsequence of an array can be obtained by erasing some (possibly
zero) elements from the array. You can erase any elements, not
necessarily going successively. The remaining elements preserve their
order. For example, for the array 5,3,1,2,4 the following arrays are
subsequences: 3, 5,3,1,2,4, 5,1,4, but the array 1,3 is not.
Input
The first line of the input containing integer number nn
(1≤n≤2⋅1051≤n≤2⋅105) — the length of the array. The second line of the
input containing nn integer numbers a1,a2,…,ana1,a2,…,an
(1≤ai≤1091≤ai≤109) — the array itself.
Output
On the first line print kk — the maximum length of the subsequence of
the given array that forms an increasing sequence of consecutive
integers.On the second line print the sequence of the indices of the any
maximum length subsequence of the given array that forms an increasing
sequence of consecutive integers.
Examples
input
7
3 3 4 7 5 6 8
output
4
2 3 5 6
input
6
1 3 5 2 4 6
output
2
1 4
input
4
10 9 8 7
output
1
1
input
9
6 7 8 3 4 5 9 10 11
output
6
1 2 3 7 8 9
思路
给出一个数组，让求出最长的连续递增子序列，先输出长度，再输出下标。
我们在进行输入的时候进行一个处理，利用map存储，当前数字的mp[x]=mp[x-1]+1,这样就可以求出以当前数字为最后一个数的最长长度,然后去找一个最大的，那么，一共有maxx个数，其中最小的数是当前的最大值减去maxx+1，然后遍历数组输出即可
代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <sstream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include<list>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define inf 0x3f3f3f3f
#define x1 hpc_x1
#define y1 hpc_y1
typedef long long ll;
const int N=2e5+20;
int a[N];
map<int,int>mp;
int main()
{
int n,x;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&x);
a[i]=x;
mp[x]=mp[x-1]+1;
}
int pos,maxx=0;
for(auto i:mp)
{
if(i.second>maxx)
{
maxx=i.second;
pos=i.first;
}
}
pos=pos-maxx+1;
printf("%d\n",maxx);
for(int i=1; i<=n; i++)
{
if(a[i]==pos)
{
printf("%d ",i);
pos++;
}
}
puts("");
return 0;
}