题目，给定一个数列，n <= 1e5 。要求找出一个区间，使得其内区间最小值 * 区间总和的值最大，要求输出区间。
首先先维护一个单调递增的栈，同时记录一个lef值表示：lef[i]表示当前栈内这个元素能匹配的最左值，什么意思呢？就是在最左边那里，它是最小的。a[lef[i] - 1] < a[lef[i]] 的。这样的话，每次弹出一个元素，我就能知道它在那个区间内最小的，左区间是lef[i]，右区间栈顶元素的位置。这样是最优的，因为你匹配多一些大的数字更好。
用simple来说
3 1 6 4 5 2
开始的时候，是3入栈，记录lef[1] = 1。我简陋写为 3 (1,1)
然后是1了，比3小，所以3出栈，3出栈后注意了，要计算，最左区间，自然是1，最右区间，就是当前栈顶元素的位置，也是1。tans = 9; 然后要跟新1的最左值，是1。
6进来，直接进。1 (1,2) ， 6 (3, 3)
然后4进来，弹出6，计算6.栈内是 1 (1,2) 4（3， 4）
5进来。栈内是 1 (1,2) 4（3， 4）5(5,5)
2进来。把5弹出，计算5.
把4弹出，注意了。区间是4的最左值，最右值是栈顶元素的位置，当前栈顶元素是5，位置是5.所以表明4在{6,4,5}最小。计算。
主要是弹出一个元素，就要对那个元素进行 计算。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 100000 + 20; int a[maxn]; int stack[maxn]; //只保存位置即可，大小关系可以调用a[stack[top]] 判断 int lef[maxn]; //传入栈的位置，就可以得到对应元素在最左区间内最小 LL sum[maxn]; void work () { int n; scanf ("%d", &n); for (int i = 1; i <= n; ++i) { scanf ("%d", &a[i]); sum[i] = sum[i - 1] + a[i]; } a[n + 1] = -1; //防止全部都是递增 LL ans = -1, L, R; int top = 0; for (int i = 1; i <= n + 1; ++i) { int TT = stack[top]; // 栈内元素到栈顶元素，这个区间最小值 int toleft = i; //保存插入后上一个元素的最左值 while (top >= 1 && a[i] < a[stack[top]]) { //等于的话，不如让它扩大 LL t = (sum[TT] - sum[lef[stack[top]] - 1]) * a[stack[top]]; if (t > ans) { ans = t; L = lef[stack[top]]; R = TT; } toleft = lef[stack[top]]; --top; // printf ("%d ", top); // printf ("%lld**** ", ans); } ++top; stack[top] = i; lef[stack[top]] = toleft; //printf ("%d %d %d ", top, lef[stack[top]], stack[top]); } printf ("%lld ", ans); printf ("%lld %lld ", L, R);; return ; } int main () { #ifdef local freopen("data.txt","r",stdin); #endif work (); return 0; }