题目链接[http://poj.org/problem?id=2796]
题意：给出一个数列，要求在这个数列里找到一个区间，使得在这个区间里的最小值*SUM[l,r]最大。
题解：思路来源于【http://acm.hdu.edu.cn/showproblem.php?pid=1506】这个题。思想是：一a[i]为某个区间的最小值，初始区间为[i,i],左端向左延伸，右端向右延伸。最后维护最大值。
但是向前向后延伸的时候不能暴力，时间不允许，这里要用到DP的思想：
定义L[MAXN]=R[MAXN]=i;对于a[i]的L[i]，刚开始的L[i]=i;如果a[i]>a[L[i]-1] -> L[i]=L[L[i]-1];2、R同理。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN = ;
LL a[MAXN], sum[MAXN];
LL L[MAXN], R[MAXN];
int n;
int main ()
{
scanf("%d", &n);
for(int i = ; i <= n; i++)
{
scanf("%lld", &a[i]);
sum[i] = sum[i - ] + a[i];
L[i] = R[i] = i;
}
a[] = a[n + ] = -;//保证不会访问或者访问无效。
for(int i = ; i <= n; i++)
{
while(a[i] <= a[L[i] - ])
L[i] = L[L[i] - ];
}
for(int i = n; i >= ; i--)
{
while(a[i] <= a[R[i] + ])
R[i] = R[R[i] + ];
}
LL ans = -, l, r;
for(int i = ; i <= n; i++)
{
LL T = a[i] * (sum[R[i]] - sum[L[i] - ]);
if(ans < T)
ans = T, l = L[i], r = R[i];
}
printf("%lld\n%lld %lld\n", ans, l, r);
}