posts - 16,comments - 0,trackbacks - 0
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*<= 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*<= y-x+1) l*=2++j;
    
if (bj < 0return 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 阅读(133) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理