【bzoj1318】 [Spoj744] Longest Permutation

2014年9月9日1,5510

Description

给你一个序列A含有n个正整数(1<=Ai<=n)。A的子集形式类如Au, Au+1 … , Av (1<=u<=v<=n),即必须是连续的。我们感兴趣的是一种子集,它含有元素包括1,2,…k。(k是子集的大小)。 你的任务是找到这种类型的最长的子集。

Input

第一行,一个数n,表示序列A的长度 第二行,n个数,第I个数表示元素Ai

Output

一个数,表示可选子集的长度

Sample Input

5
4 1 2 3 2

Sample Output

4

HINT

你可以选得子集从A1开始到A4,这个子集长度为4,包含了1,2,3,4)
1<=n<=100010

题解

对于一个题中要求的数列。必然满足条件:

A.数列中元素都不同

B.数列中元素和为(q+1)*q/2 (q为最大值)

c.数列中包含1

枚举每个1,例如a[x]=1,假定最大值在x的左边

向左扫描的过程中不断更新最大值即数列长度。。

通过记录前缀和该数后面第一个出现相同的数的位置

设最大值为len。。。向右最早出现相同的数的位置r也不断要更新。。

比如当前到了i。i+len<r且sum[i+len-1]-sum[i-1]=len*(len+1)/2 可以用len更新答案。

把数列翻转一下再做一遍