ＲＴ
思路是:
设读入的数组为s[],
//找数组中连续j个数组成的串
//该串以s[i]开头,以s[i+j-1]为尾,p为正中间（偏后）的数
//例如：对于数组[3,1,5,6,8,1,7],
   i=2,j=4时,该子串为[1,5,6,8];p为4,s[p]=6;

核心：max[2,3,4,5]等于max[2,3]与max[4,5]中的较大值
      即dp[i][i+j-1]=max(dp[i][p-1],dp[p][i+j-1]);
     如此可以找出长为2,4,8,16…的串中最大（小）数
//则对于任意长度串:如max[2,3,5,7,1,6],求max[2,3,5,7]与max[5,7,1,6]中大值即可

由于空间不够，只好开成滚动数组
dp[i]表示以i开头连续j个数中最大值，dps[i]则是最小值，dp[i],dps[i]初值都等于s[i]，
代码就是：
（下标从1开始）
for(j=2;j<=k;j*=2)
    for(i=1,p=j;p<=n;i++,p++)  
        {
         if(dp[p]>dp[i])  dp[i]=dp[p]; 
         if(dps[p]<dps[i])dps[i]=dps[p];
        }
下面是输出：
j/=2;
for(i=1,p=k-j+1,m=n-k+1;i<=m;i++,p++)
     printf("%d ",dps[i]<dps[p]?dps[i]:dps[p]);
printf("\n");
for(i=1,p=k-j+1,m=n-k+1;i<=m;i++,p++)
     printf("%d ",dp[i] > dp[p]? dp[i]: dp[p]);
printf("\n");

WHY　　ＷＡ？？？
那位大牛请指点一二，感激不尽！！！

• WA的代码…… (1025) JokerKS 2010-10-04 15:08:11
  • Re:已解决……5600MS…… (1125) JokerKS 2010-10-05 12:04:54