hdu 1506（动态规划，很棒的优化）

这道题直接按照一般的思路去算是要超时的，必须经过一定程度的优化。

对于a[i]，我们需要记录的是他之前和之后最大的连续的值比a[i]大的长度，如果每次都一个个去比对，数据大小是100000，时间复杂度是O(n^2)，超时那是必然的。但是其实对于a[i]来说，如果去求后面连续的值，完全没必要一个个去比对，直接看a[i-1]的值就行了。

比如说2、3、4、5这个序列，如果我们要看3往后能延伸多长，并不需要去逐个和4和5比较，在计算4的时候，我们已经计算过5是比4大的，因为3比4小，4所能往后延伸的长度，3也一定能达到（4能延伸的长度内的数据都大于等于4，当然也都比3大），我们可以直接比较在4达到的最终长度的末端之后的值。

这道题计算的时候进制转换也需要特别注意，如果temp没有强制转换成__int64位，提交会wa。

这道题优化的思路非常巧妙，很值得学习。

[cpp]
#include<stdio.h>
#define N 100005
int a[N],s[N],e[N];
int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        int i;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            s[i]=e[i]=i;
        }
        for(i=0;i<n;i++)
        {
            while(s[i]>=1&&a[s[i]-1]>=a[i])
                s[i]=s[s[i]-1];
        }
        for(i=n-1;i>=0;i--)
        {
            while(e[i]<n-1&&a[e[i]+1]>=a[i])
                e[i]=e[e[i]+1];
        }
        __int64 ans;
        ans=0;
        for(i=0;i<n;i++)
        {
            __int64 temp;
            temp=(__int64)(e[i]-s[i]+1)*a[i];//这里需要进行强制转换。
            if(temp>ans)
                ans=temp;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

#include<stdio.h>
#define N 100005
int a[N],s[N],e[N];
int main()
{
int n;
while(scanf("%d",&n),n)
{
  int i;
  for(i=0;i<n;i++)
  {
   scanf("%d",&a[i]);
   s[i]=e[i]=i;
  }
  for(i=0;i<n;i++)
  {
   while(s[i]>=1&&a[s[i]-1]>=a[i])
    s[i]=s[s[i]-1];
  }
  for(i=n-1;i>=0;i--)
  {
   while(e[i]<n-1&&a[e[i]+1]>=a[i])
    e[i]=e[e[i]+1];
  }
  __int64 ans;
  ans=0;
  for(i=0;i<n;i++)
  {
   __int64 temp;
   temp=(__int64)(e[i]-s[i]+1)*a[i];//这里需要进行强制转换。
   if(temp>ans)
    ans=temp;
  }
  printf("%I64d\n",ans);
}
return 0;
}

补充：软件开发 , C++ ,