问道ACM题,Problem DescriptionGiven a number sequence A with n n

问道ACM题,
Problem Description
Given a number sequence A with n numbers,you task is to find the max A[i]-A[j] which i

这一道题可以用求区间最值的方法解决主要就是RMQ和线段树或树状数组算法,参考http://baike.baidu.com/link?url=ag6ty7JO80bNLjm4ZvfWL7jQbgfukKQRP6ogfTC8-XjmNJOcL6UOgd2hSw_ht1qG2bSZR8tL-vM5noff-BFiPK#4_3.代码：#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<sstream>
#include<cstring>
#include<math.h>
#include<stdio.h>
#include<map>
#include<set>
using namespace std;
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#define MN 100005
int mi[MN][17],mx[MN][17],w[MN];
int n;
void rmqinit()
{
int i,j,m;
for(i=1;i<=n;i++){mi[i][0]=mx[i][0]=w[i];}
m=int(log(n)/log(2.0));
for(i=1;i<=m;i++)
{
for(j=n;j>=1;j--)
{
mx[j][i]=mx[j][i-1];
if(j+(1<<(i-1))<=n)
mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
mi[j][i]=mi[j][i-1];
if(j+(1<<(i-1)<=n))
mi[j][i]=min(mi[j][i],mi[j+(1<<(i-1))][i-1]);
}
}
}

int rmqmin(int l,int r)
{
int m=int(log(r-l+1)/log(2.0));
return min(mi[l][m],mi[r-(1<<m)+1][m]);
}

int rmqmax(int l,int r)
{
int m=int(log(r-l+1)/log(2.0));
return max(mx[l][m],mx[r-(1<<m)+1][m]);
}

int main()
{
int i,T=1;
while(cin>>n){
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);//cin>>w[i];
rmqinit();
int ans=w[1]-w[2];
int tmp;
for(i=2;i<=n-1;i++){
tmp=rmqmax(1,i)-rmqmin(i+1,n);
if(tmp>ans)
ans=tmp;
}
printf("Case %d: %d\n",T++,ans);
}
return 0;
}