区间贡献法

929code / 2023-05-19 / 原文

1. 英雄的力量（数学规律）

2. 子数组的最小值(最大值)之和

3. 子数组的最小乘积的最大值

单调栈+前缀和

class Solution {
public:
    int maxSumMinProduct(vector<int>& arr) {
        const int mod = 1e9+7;
        //由于是正数，只用计算最大区间即可
        //先求最小值区间
        int n = arr.size();
        vector<int> monoStack; //单调栈
        vector<int> left(n), right(n);//左右边界
        for (int i = 0; i < n; i++) {//从左往右找左边更小值
            while (!monoStack.empty() && arr[i] <= arr[monoStack.back()]) {//把更大的值挤出来，相等的视为更大，区间计算的时候不影响
                monoStack.pop_back();
            }
            left[i] = monoStack.empty() ? 0 : monoStack.back()+1; //左边界
            monoStack.emplace_back(i);//放入坐标
        }
        monoStack.clear();
        for (int i = n - 1; i >= 0; i--) { //从右往左找右边更小值
            while (!monoStack.empty() && arr[i] < arr[monoStack.back()]) {
                monoStack.pop_back();
            }
            right[i] = monoStack.empty() ? n : monoStack.back(); //右边界
            monoStack.emplace_back(i);
        }

        vector<long long> presum(n+1);
        for(int i=0;i<n;i++)
            presum[i+1] = presum[i]+arr[i];

        long long ans = 0;
        for (int i = 0; i < n; i++)  //计算以当前值为最小值最大区间的最小乘积
            ans = max(ans,(presum[right[i]]-presum[left[i]])*arr[i]);
        return ans%mod;
    }
};