已知一个有 n 个数序列 a[i] ，在序列 a 中的区间 [l,r] 中的最小值为 a[p] ， 求
a[p]*(a[l]+a[l+1]+...+a[r]) 的最大值为多少？
★数据输入
第一行是一个整数n
第二行为n 个整数对应 a[i]
对于50%数据
1 <= n <= 5000
对于100%数据
1 <= n <= 100 000
1<=a[i]<=1000000
★数据输出
如题意所示
输入示例 输出示例
6 60
3 1 6 4 5 2
# include<stdio.h>
# define MAX 100002
int start [MAX];
int end[MAX];
__int64 data[MAX];
__int64 sum[MAX];
int main()
{
int n;
while(~scanf("%d",&n))
{
data[0] = -1;
data[n+1] = -1;
int i = 1;
int j;
for(i=1;i<=n;i++)
{
scanf("%d",&data[i]);
for(j=i-1;j>=0;)
{
if(data[i] > data[j])
{
start[i] = j + 1;
break;
}
else
j = start[j] - 1;
}
}
for(i=n;i>=1;i--)
{
for(j=i+1;j<=n+1;)
{
if(data[i] > data[j])
{
end[i] = j - 1;
break;
}
else
j = end[j] + 1;
}
}
sum[0] = 0;
for(i=1;i<=n;i++)
sum[i] = sum[i-1] + data[i];
__int64 answer = -1;
for(i=1;i<=n;i++)
{
__int64 temp = (sum[end[i]] - sum[start[i]-1]) * data[i];
if(temp > answer)
answer = temp;
}
printf("%I64d\n",answer);
}
return 0;
}