学步园

题目链接：http://acm.hdu.edu.cn/diy/contest_showproblem.php?cid=18800&pid=1003

题目分析：其实就是找最大的回文串，不过是对这个回文串有点附加的要求罢了。在o(n)求最大回文串，参考我的另一篇博客：http://blog.csdn.net/kay_zhyu/article/details/8712815

PS：这道题其实我没有AC过，每次都是wrong answer。人世间最郁闷的事就是你觉得程序没有任何问题，但是AC的时候，一直提示wrong answer。感觉我用很多例子测试都是对的啊。可能自己考虑得还不够全面。如果有大神路过，帮忙指点指点，菜鸟感激不尽。

#include <stdio.h>

#define M 200010

int p[M];
int str[M];

inline int min(int a, int b)
{
	return a < b ? a : b;
}

void kp(int n)//找最长的回文
{
	int i;
	int mx = 0;
	int ID;

	for(i = 1; i < n; ++i)
	{
		if(mx > i)
		{
			p[i] = min(p[ID * 2 - i], mx - i);
		}
		else
		{
			p[i] = 1;
		}
		while((i - p[i] >= 1) && (i + p[i] < n) && (str[i - p[i]] == str[i + p[i]]))
		{
			if(str[i - p[i]] <= str[i - p[i] + 1] || str[i] == -1 ||  
				(str[i - p[i] + 1] == -1 && str[i - p[i]] <= str[i - p[i] + 2]))//这是针对这道题的附加条件附加的判断
			{
				++p[i];
			}
			else
			{
				break;
			}
		}

		if(i + p[i] > mx)
		{
			mx = i + p[i];
			ID = i;
		}
	}
}

void main()
{
	int n;
	int t;
	int i;
	scanf("%d",&t);

	while(t--)
	{
		scanf("%d",&n);
		str[0] = -2;
		str[1] = -1;
		i = 1;
		while(n--)
		{
			scanf("%d",&str[++i]);
			str[++i] = -1;
		}
		n = i + 1;

		int nMax = 0;
		kp(n);

		for(int i = 1; i < n; ++i)
		{
			nMax = nMax > p[i] ? nMax : p[i];
		}
		printf("%d\n", nMax - 1);
	}
}