区间贡献法
发布时间 2023-05-19 21:06:27作者: 失控D大白兔
3. 子数组的最小乘积的最大值
单调栈+前缀和
```
class Solution {
public:
int maxSumMinProduct(vector& arr) {
const int mod = 1e9+7;
//由于是正数，只用计算最大区间即可
//先求最小值区间
int n = arr.size();
vector monoStack; //单调栈
vector 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;
}
};
</details>
####4. [巫师的总力量和](https://www.cnblogs.com/929code/p/17416307.html)