$O(N)$ 单调栈

我们需要找到一个连续的子数组，使得该子数组的最小值乘以子数组的和最大。

单调栈的应用： 利用单调栈来高效地找到每个元素作为最小值时的最大区间。单调栈可以帮助我们维护一个递增的序列，从而快速确定每个元素的最小值影响范围。

前缀和数组： 预先计算前缀和数组 $sum$ ，其中 $sum[i]$ 表示数组 $a$ 前 $i$ 个元素的和。这样可以在 $O(1)$ 时间内计算任意子数组的和。

遍历与更新： 遍历数组，使用单调栈来找到每个元素作为最小值时的左右边界，计算当前子数组的 $min * sum$ ，并更新最大值。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 2e5 + 10, M = 30;

int a[N];
int n;
int stk[N], top = -1;
int sum[N];

void solve() 
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        while(top >= 0 && a[stk[top]] >= a[i])
        {
            int x = a[stk[top]];
            top --;
            int l = top == -1 ? 0 : stk[top];
            ans = max(ans, (sum[i - 1] - sum[l]) * x);
        }
        stk[++ top] = i;
    }
    
    while(top != -1)
    {
        int x = a[stk[top]];
        top --;
        int l = top == -1 ? 0 : stk[top];
        ans = max(ans, (sum[n] - sum[l]) * x);
    }
    cout << ans << endl;
    
}            

int main()
{
    int t = 1;
    // cin >> t;
    while(t --)
        solve();
}