這道題直接按照一般的思路去算是要超時的，必須經過一定程度的優化。
對於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;
}
