该题目可以用辅助数组l[i], r[i]来指向以data[i]为最小值的左端点和右端点。然后最后枚举每个data[i]寻找每个data[i]的美丽值的最大值。
然后辅助数组可以用单调栈求出。
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define N 2001011
#define int long long
using namespace std;
int n, top, maxn, data[N], stac[N], r[N], l[N]; //l 和 r分别表示以当前位置的值为最小值的连续区间的左右端点。
inline int read()
{char ch; int now = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') now = now * 10 + ch - '0', ch = getchar();
return now;
}
signed main()
{
n = read();
for (int i = 1; i <= n; i++)
data[i] = read(), l[i] = 1, r[i] = n; // 栈里存当前美丽系数最大值。
for (int i = 1; i <= n; i++)
{
while (top && data[i] <= data[stac[top]]) // 如果当前值比data[i]要小
r[ stac[top--] ] = i - 1;
l[i] = stac[top] + 1; //
stac[++top] = i;
}
for (int i = 1; i <= n; i++)
maxn = max(maxn, (r[i] - l[i] + 1) * data[i]);
printf("%lld", maxn);
return 0;
}