题意：给n个数（n<=5e5），定义一个区间的值为，区间内最小的值乘区间和。求n个数所有区间中的最大值。

思路：为了考虑到所有的情况，我们可以枚举每个数字作为最小值时，它所产生的区间的最大值，那么对于一个数字作为最小值，通过单调栈，可以找到这个数字最左最右的区间，在这个区间内，可以通过前缀和来求每个区间的最大和

当a[i]>0,用前缀和最大值-前缀和最小值,得区间和最大值

a[i]<0,用前缀和最小值-前缀和最大值，得区间和最小值。

注意：如何用单调栈求每个数的区间，我求的是开区间，我们可以用栈来维护一个单调递增的序列，遍历每个数字，当遇到大于栈顶的数字时，往里放数字，当遇到小于栈顶的数字时，往出拿数字，对于要拿的每个数字来说，这个往里放的数字就是它们的右边界，同时对于往里放的每个数字来说，它左边是一个递增的序列，它左边第一个位置就是它的左边界了。

所以：对于一个单调栈，当它进栈的时候，栈中上一个元素的位置，就是左边界，当它出栈的时候，就是它的右边界。

注意：用前缀和来求一个n个数区间内最值时，前缀和大小为n+1，第一个前缀和内为空。

这里lmin[],rmin[]求的是每一个数字的左右开区间，求区间最值时,是n个数字中[i,r-1]的前缀和最值-[l,i-1]的前缀和最值。

 

#include
     
      using namespace std;#define ll long longconst int maxn=5e5+5;ll dpmin[maxn][25],dpmax[maxn][25];int a[maxn];ll sum[maxn];void initrmq(int n){    int i, j;    for(i=1; i<=n; i++)    {        dpmin[i][0]=sum[i];        dpmax[i][0]=sum[i];    }    int x = 0;    while((1<
      
       <= n) ++x;    for(j=1; j<=x; j++)        for(i=1; i+(1<
       
        <=n; i++)        {            dpmin[i][j]=min(dpmin[i][j-1], dpmin[i+(1<<(j-1))][j-1]);            dpmax[i][j]=max(dpmax[i][j-1], dpmax[i+(1<<(j-1))][j-1]);        }}ll queryrmq(int l, int r, int op) // 传入op=0,表示最小值，op=1，表示最大值{    l++;    r++;    int k=log2(r-l+1);    if(op==0)        return min(dpmin[l][k], dpmin[r-(1<
        
         0)            ans=max(ans,(ll)a[i]*(queryrmq(i,rmin[i]-1,1)-queryrmq(lmin[i],i-1,0)));        else            ans=max(ans,(ll)a[i]*(queryrmq(i,rmin[i]-1,0)-queryrmq(lmin[i],i-1,1)));    }    printf("%lld",ans);}