RMQ+遞歸；
# include <stdio.h>
# define N 50005
# define L 16
int n, a[N], mn[N][L], mx[N][L];
int ans;
int Max_t(int x, int y)
{
return a[x] > a[y] ? x : y;
}
int Min_t(int x, int y)
{
return a[x] < a[y] ? x : y;
}
void init(void)
{
int i;
ans = -1;
for (i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
mn[i][0] = i;
mx[i][0] = i;
}
}
void pre(void)
{
int l, j, i;
for (j = 1, l = 1; l*2 <= n; ++j, l*=2)
for (i = 1; i+2*l <= n+1; ++i)
{
mn[i][j] = Min_t(mn[i][j-1], mn[i+l][j-1]);
mx[i][j] = Max_t(mx[i][j-1], mx[i+l][j-1]);
}
}
int rmq(int x, int y, int bj)
{
int j = 0, l = 1;
while (2*l <= y-x+1) l*=2, ++j;
if (bj < 0) return Min_t(mn[x][j], mn[y-l+1][j]);
else return Max_t(mx[x][j], mx[y-l+1][j]);
}
void cal(int s, int t)
{
int x, y;
if (s >= t) return ;
x = rmq(s, t, -1);
y = rmq(s, t, 1);
if (x == y) return ;
if (x < y)
{
ans = y-x>ans ? y-x:ans;
if (s < x) cal(s, x-1);
if (y < t) cal(y+1, t);
}
else
{
if (s < y) cal(s, y);
cal(y+1, x-1);
if (x < t) cal(x, t);
}
}
int main()
{
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
while (~scanf("%d", &n))
{
init();
pre();
cal(1, n);
printf("%d\n", ans);
}
return 0;
}
posted on 2012-08-27 09:43
yajunw 閱讀(148)
評(píng)論(0) 編輯 收藏 引用