定义dp[i][j]为起始位置为i，终点为i+2^j-1的区间的最大值/最小值； 转移方程 dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]) 具体代码：
void st(int n){ for(int i=1;i<=n;++i) dp[i][0]=p[i].w; int len=log(n)/log(2)+1;//区间长度为n的二进制最大数，满足2^len>n for(int i=1;i<len;++i){ int s=1<<(i-1); for(int j=1;j<=n-(1<<i)+1;++j){ dp[j][i]=max(dp[j][i-1],dp[j+s][i-1]); } } } int query(int l,int r){ int len=log(r-l+1)/log(2);//满足2^len<r-l+1<=2^(len+1) return max(dp[l][len],dp[r-(1<<len)+1][len]);l+ //答案一定在[l,l+2^len-1]和[r-2^len+1,r]，这两个区间是相邻或者相交的，因为长度相加为2^(len+1)>=r-l+1>2^len。 }练习：POJ3368 思路： 因为序列是单调的，所以我们可以离散化，对于连续相同数值的区间缩为一个点，点包含l，r和区间长度； 对于一个区间如果满足a[l]==a[r] ，就输出r-l+1；（区间的数值都相同，一个区间） 否则就在左右两边的区间跟中间的区间找最大值。（两个或多个不同区间的情况） 代码：
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; const int maxn=1e5+11; const int mod=1e9+7; const double eps=0.000001; typedef long long ll; typedef long double lb; typedef double db; struct D{ int l,r,w; }p[maxn]; int dp[maxn][25],pos[maxn],a[maxn]; void st(int n){ for(int i=1;i<=n;++i) dp[i][0]=p[i].w; int len=log(n)/log(2)+1; for(int i=1;i<len;++i){ int s=1<<(i-1); for(int j=1;j<=n-(1<<i)+1;++j){ dp[j][i]=max(dp[j][i-1],dp[j+s][i-1]); } } } int query(int l,int r){ if(r<l) return 0; int len=log(r-l+1)/log(2); return max(dp[l][len],dp[r-(1<<len)+1][len]); } int main(){ int n,q,id,l,r; while(scanf("%d",&n)==1&&n){ scanf("%d",&q); id=1; p[id].l=pos[1]=1; for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=2;i<=n;++i){ if(a[i]!=a[i-1]){ p[id].r=i-1; p[id].w=i-p[id].l; p[++id].l=i; } pos[i]=id; } p[id].r=n,p[id].w=n-p[id].l+1; st(id); while(q--){ scanf("%d%d",&l,&r); if(pos[l]==pos[r]) printf("%d\n",r-l+1); else{ int a1=p[pos[l]].r-l+1; int a2=r-p[pos[r]].l+1; int a3=query(pos[l]+1,pos[r]-1); int ans=max(max(a1,a2),a3); printf("%d\n",ans); } } } system("pause"); }