pku2452.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 70 行

#include <stdio.h>

int dismm;

void find(int *a, int s, int e)
{
	int i, min, max, maxdis, t;
	min = s;
	max = s;
	
	if (e - s <= dismm)
	{
		return;
	}

	for (i = s; i <= e; i++)
	{
		if (a[i] > a[max])
		{
			max = i;
		}
		if (a[i] < a[min])
		{
			min = i;
		}
	}
	if (max > min)
	{
		maxdis = max - min;
		if (dismm < maxdis)
		{
			dismm = maxdis;
		}
		find(a, s, min - 1);
		find(a, max + 1, e);
	}
	else
	{
		find(a, s, max);
		find(a, max + 1, min - 1);
		find(a, min, e);
	}
}

int main()
{
	int N, a[50001], t, i;
	
	while (scanf("%d", &N) != -1)
	{
		dismm = 0;
		for (i = 0; i < N; i++)
		{
			scanf("%d", &a[i]);
		}
		find(a, 0, N - 1);
		if (dismm == 0)
		{
			printf("-1\n");
		}
		else
		{
			printf("%d\n", dismm);
		}
	}

	return 0;
}