题目
思路：首先预处理前缀和，然后用单调栈求出答案。
理解单调栈
AC代码：
#include <cstdio>
#include <iostream>
#include <stack>
#include <string.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> iip;
typedef pair<ll, ll> llp;
const int MAXN = 200005;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int i, j, n, a[MAXN], l[MAXN], r[MAXN], top;
ll ans;
stack<int> s;
int main()
{
while(scanf("%d", &n) != EOF && n) {
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
ans = 0;
for(i = 0; i < n; i++) {
while(!s.empty() && a[i] < a[s.top()]) {
r[s.top()] = i;
s.pop();
}
if(s.empty()) l[i] = 0;
else if(a[i] == a[s.top()]) l[i] = l[s.top()];
else l[i] = s.top() + 1;
s.push(i);
}
while(!s.empty()) {
r[s.top()] = i;
s.pop();
}
for(i = 0; i < n; i++) {
ans = max(ans, 1ll * a[i] * (r[i]-l[i]));
}
printf("%lld\n", ans);
// cout.flush();
}
return 0;
}
