POJ2796 Feel Good（单调栈）

题意：

给出一列数据，要求一个区间内最小值与区间内数据总和乘积最大值

要点：

还是单调栈，这次我自己写的，先做了几题比较简单的果然还是有效果的，这题也是一样，按点遍历，网上大神做的是直接遍历一次即可，我看不太懂，还是自己写了一个往两侧寻找边界的，比较好理解，注意这题可以开一个sum数组存储第i个数据前的和，这样降低了复杂度，这是一个比较方便的技巧，注意sum数组也要设成long long型，因为题目里数据最大可以是1E6，开始我就是WA在这里了。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 100005
int stack[maxn], a[maxn];
int l[maxn], r[maxn];
long long sum[maxn];//注意sum数组也要是long long型的int main()
{int n,i,top;while (scanf("%d", &n) != EOF){memset(sum, 0, sizeof(sum));for (i = 1; i <= n; i++){scanf("%d", &a[i]);sum[i] = sum[i - 1] + a[i];}top = 0;for (i = 1; i <= n; i++)//找左边界{while (top > 0 && a[stack[top - 1]] >= a[i])top--;l[i] = top == 0 ? 1 : stack[top - 1] + 1;stack[top++] = i;}top = 0;for (i = n; i >= 1; i--)//找右边界{while (top > 0 && a[stack[top - 1]] >= a[i])top--;r[i] = top == 0 ? n : stack[top - 1] - 1;stack[top++] = i;}long long max = -1, temp;int rr, ll;for (i = 1; i <= n; i++){temp = a[i] * (sum[r[i]] - sum[l[i] - 1]);if (max < temp){max = temp;ll = l[i];rr = r[i];}}printf("%lld\n", max);printf("%d %d\n", ll, rr);}return 0;
}