- 先说这题的关键性质：每一个数应该只会计算一次，它有一个最小区间[L,R]，即它在这个区间内是最小的，最小区间内任何包含它的子区间都不会大于F(L,R)=（a[L]+...+a[R]）*min（a[l]..a[R]），只需要计算一次就可以不再计算其他子区间。
- 利用这个性质，可以得到这样的做法，如果能知道任意区间的最小值，就能不断递归去删点，就能轻松分割出每个点的最小区间。可以用线段树在O(lgn)复杂度快速得到 区间的最小值及其下标，总时间复杂度就是O(nlgn)。
但是，理想是美好的，AC是做不到的，因为会出现栈溢出，递归共有n个节点，每个节点需要求一次最小值，利用线段树求最小值的复杂度是lgn，递归太深，当n=20000时就GAME OVER了，但是UVA给我返回一个WA是什么情况，害的我看了一天，也怪自己太年轻。刚才又改了一下直接超时了，看了必然要用O（n）的算法了。但是，上面说的方法一定是对的。
正确高效的做法就是利用栈维护一个递增序列。
例如对于数据3 1 6 4 5 2
当i=1时，a[i]=3,栈为空，那么3的区间下限就是1，下标1入栈
当i=2时，a[i]=1,栈顶为1，a[1]=3，大于a[2]，出栈，此时栈又是空，1的下限为1，下标2入栈
当i=3时，a[i]=6,栈顶为2，a[2]=1，小于6，那么6的下限就是2+1，6的下标入栈
当i=4时，a[4]=4,栈顶为4，a[4]=6大于4，6出栈，此时站顶为a[2]=1，小于4,4的下限为2+1，4入栈
后面都是同样的道理，将序列的下标存入栈中，方便得到下限，当栈为空说明从1到当前位置这个区间它就是最小值，就直接把下限设为1，否则就等于比它小的那个数的下标+1
得到下限，然后原数组翻转用同样的方法就能得到上限，这样每个数的最下区间就找到了。
AC代码：
#include<cstdio>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
LL sum[maxn];
int left[maxn],right[maxn],d[maxn];
int n;
void solve(int *a,int *res){
stack<int>sta; //记录下标
for(int i=1;i<=n;++i){
while(!sta.empty()&&a[i]<=a[sta.top()]){
sta.pop();
}
if(sta.empty()) res[i]=1;
else res[i]=sta.top()+1;
sta.push(i);
}
}
int main(){
sum[0]=d[0]=0;
int kase=0;
while(scanf("%d",&n)==1){
if(kase++) printf("\n");
for(int i=1;i<=n;++i){
scanf("%d",&d[i]);
//d[i]=1000000;
sum[i]=sum[i-1]+d[i];
}
solve(d,left);
//反转
int x=1,y=n;
while(x<y){
swap(d[x],d[y]);
++x;
--y;
}
solve(d,right);
x=1,y=n;
while(x<y){
swap(right[x],right[y]);
++x;
--y;
}
for(int i=1;i<=n;++i) right[i]=n+1-right[i];
LL ans=(LL)d[n]*d[n];
int ll=1,rr=1;
for(int i=1;i<=n;++i){
int l=left[i],r=right[i];
LL temp=(sum[r]-sum[l-1])*d[n-i+1];
if(temp>ans){
ll=l,rr=r;
ans=temp;
}
}
printf("%lld\n%d %d\n",ans,ll,rr);
}
return 0;
}贴下线段树的做法（超时而且栈溢出）：
#include<cstdio>
#include<algorithm>
#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
LL sum[maxn];
int n;
int c=0;
struct point{
LL val;
int ind;
}tr[maxn*6];
point min(point &a,point &b){
return a.val<b.val?a:b;
}
void Build(int l,int r,int cur){ //方便查找区间最小值
if(l==r) {
++c;
tr[cur].val=sum[c]-sum[c-1];
tr[cur].ind=c;
return;
}
int mid=(l+r)>>1;
Build(l,mid,cur<<1);
Build(mid+1,r,(cur<<1)+1);
tr[cur]=min(tr[cur<<1],tr[(cur<<1)+1]);
}
point Search(int l,int r,int ll,int rr,int cur){ //查找区间[l,r]的最小值
if(l==ll&&r==rr) return tr[cur];
int mid=(ll+rr)>>1;
if(r<=mid) return Search(l,r,ll,mid,cur<<1);
else if(l>=mid+1) return Search(l,r,mid+1,rr,(cur<<1)+1);
else {
point a=Search(l,mid,ll,mid,cur<<1);
point b=Search(mid+1,r,mid+1,rr,(cur<<1)+1);
return min(a,b);
}
}
struct node{
int l,r;
LL val;
node(){
}
node(int l,int r,LL val):l(l),r(r),val(val){
}
};
node max(node &a,node &b){
return a.val>b.val?a:b;
}
node dfs(int x,int y){
if(y<x) return node(1,1,sum[1]*sum[1]);
if(x==y) return node(x,y,(sum[y]-sum[y-1])*(sum[y]-sum[y-1]));
point Min=Search(x,y,1,n,1);
printf("%d %d %lld %d\n",x,y,Min.val,Min.ind);
node ans=node(x,y,(sum[y]-sum[x-1])*Min.val);
int ind=Min.ind;
node a=dfs(x,ind-1);
node b=dfs(ind+1,y);
ans=max(ans,a);
return max(ans,b);
}
int main(){
int kase=0;
while(scanf("%d",&n)==1){
if(kase++) {
printf("\n");
}
int v;
sum[0]=0;
for(int i=1;i<=n;++i){
scanf("%d",&v);
sum[i]=sum[i-1]+v;
}
c=0;
Build(1,n,1);
node ans=dfs(1,n);
printf("%lld\n%d %d\n",ans.val,ans.l,ans.r);
}
return 0;
}如有不当之处欢迎指出！