记录编号	155878	评测结果	AAAAAAAAAAAAAAA
题目名称	乐曲主题	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2015-03-31 17:58:47	内存使用	0.38 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
const double eps=1e-10;
///==============struct declaration==============

///==============var declaration=================
const int MAXN=5010;
int n,k;
int Dx[MAXN];
int sa[MAXN],rank[MAXN],trank[MAXN],h[MAXN];
///==============function declaration============
bool cmp1(int a,int b){return Dx[a]<Dx[b];}
bool cmp2(int a,int b){return rank[a]==rank[b]?rank[a+(1<<k)]<rank[b+(1<<k)]:rank[a]<rank[b];}
bool check(int length);
void SuffixArray();
///==============main code=======================
int main()
{
	//#define FILE__
	//#ifdef FILE__
   freopen("theme.in","r",stdin);
   freopen("theme.out","w",stdout);
	//#endif 
	scanf("%d",&n);int prev=0;scanf("%d",&prev);
	for(int i=1;i<=n;i++){
		int v;scanf("%d",&v);
		Dx[i]=v-prev;prev=v;				  	 
	}Dx[n]=-INF;
	SuffixArray();
	int low=3,high=(n-1)/2,mid;
	while (low<high){
		mid=(low+high+1)>>1;
		if (check(mid))
			low=mid;
		else
			high=mid-1;
	}
	if (low==3)
		printf("0\n");
	else
		printf("%d\n",low+1);
   return 0;
}
///================fuction code====================
void SuffixArray(){
	for(int i=1;i<=n;i++)
		sa[i]=i;
	sort(sa+1,sa+1+n,cmp1);
	rank[sa[1]]=1;
	for(int i=2;i<=n;i++)
		if (Dx[sa[i]]==Dx[sa[i-1]])
			rank[sa[i]]=rank[sa[i-1]];
		else
			rank[sa[i]]=rank[sa[i-1]]+1;
	for(k=0;(1<<k)<=n;k++){
		sort(sa+1,sa+1+n,cmp2);
		trank[sa[1]]=1;
		for(int i=2;i<=n;i++)
			if (rank[sa[i]]==rank[sa[i-1]]&&rank[sa[i]+(1<<k)]==rank[sa[i-1]+(1<<k)])
				trank[sa[i]]=trank[sa[i-1]];
			else
				trank[sa[i]]=trank[sa[i-1]]+1;
		for(int i=1;i<=n;i++)
			rank[i]=trank[i];
		if (rank[sa[n]]==n) break;
	}
	for(int i=1;i<=n;i++){
		h[rank[i]]=max(0,h[rank[i-1]]-1);
		int p=i,q=sa[rank[i]-1];
		while (Dx[p+h[rank[i]]]==Dx[q+h[rank[i]]]&&p+h[rank[i]]<=n&&q+h[rank[i]]<=n)
			h[rank[i]]++;
	}
	/*for(int i=2;i<=n;i++){
		for(int j=sa[i];j<n;j++)
			printf("%d ",Dx[j]);
		printf("   %d\n",h[i]);
	}*/
}
bool check(int length){
	int i=1,j;
	while (i<n){
		int j=i+1,_max=sa[i],_min=sa[i];
		while (j<=n&&h[j]>=length){
			_max=max(_max,sa[j]);
			_min=min(_min,sa[j]);
			j++;
		}
		if (_max-_min>length) return true;
		i=j;
	}
	return false;
}