LeetCode 1856. 子数组最小乘积的最大值（前缀和 + 单调栈）

示例 1：
输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14 。

示例 2：
输入：nums = [2,3,3,1,2]
输出：18
解释：最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。
3 * (3+3) = 3 * 6 = 18 。

示例 3：
输入：nums = [3,1,5,6,4,2]
输出：60
解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。
4 * (5+6+4) = 4 * 15 = 60 。
 
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^7

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        int n = nums.size();
        vector<long long> presum(n);
        for(int i = 0; i < n; i++)
            presum[i] = (i > 0 ? presum[i-1] : 0) + nums[i];//前缀和
        vector<int> left(n, 0), right(n, n-1);//每个位置为最小值的情况下，区间左右极限位置
        stack<int> s;
        for(int i = 0; i < n; i++)//顺序遍历，求左边界限
        {
            while(!s.empty() && nums[i] <= nums[s.top()])
                s.pop();//左边比我大，我是最小的
            if(!s.empty())
                left[i] = s.top()+1;//左边比我小了，我不是最小的，左边界是 栈顶的值+1位置
            s.push(i);
        }
        while(!s.empty())
            s.pop();
        for(int i = n-1; i >= 0; i--)//逆序遍历求右边界
        {
            while(!s.empty() && nums[i] <= nums[s.top()])
                s.pop();//右边比我大，我是最小的
            if(!s.empty())
                right[i] = s.top()-1;//右边有比我小的，我不是最小的，右边界是 栈顶的值-1位置
            s.push(i);
        }
        long long ans = 0;
        for(int i = 0; i < n; i++)
        {
            int l = left[i], r = right[i];//左右边界
            ans = max(ans, (presum[r]-(l>0?presum[l-1]:0))*nums[i]);
        }
        return ans%(1000000007);
    }
};