LeetCode 5752. 子数组最小乘积的最大值
原题链接
中等
作者:
0weili
,
2021-05-09 14:25:33
,
所有人可见
,
阅读 332
算法1
(枚举最小值+前缀和+单调栈) $O(n)$
C++ 代码
class Solution {
private:
using ll = long long;
const static int maxn = 1e5;
int lbound[maxn+10], rbound[maxn+10];
ll pre[maxn+10];
void cal_bound(vector<int>& nums) {
int n = nums.size();
stack<int> stk;
for(int i = 0; i < n; i++) rbound[i] = n;
memset(lbound, -1, sizeof(int) * n);
// rbound严格,lbound不严格
// 但是对于多个相同的值,最左的一个的lbound是严格的
// 对于同一个min,最宽左右边界才决定ans,不影响结果
for(int i = 0; i < n; i++) {
while(stk.size() && nums[i] < nums[stk.top()])
rbound[stk.top()] = i, stk.pop();
if(stk.size()) lbound[i] = stk.top();
stk.push(i);
}
}
public:
int maxSumMinProduct(vector<int>& nums) {
int n = nums.size();
cal_bound(nums);
pre[0] = 0;
for(int i = 1; i <= n; i++) pre[i] = pre[i-1] + nums[i-1];
ll ans = 0;
for(int i = 0; i < n; i++) {
int l = lbound[i] + 1, r = rbound[i] - 1;
ans = max(ans, nums[i] * (pre[r+1] - pre[l]));
}
return ans % ((int)1e9+7);
}
};
// 思路要转变过来。。。
// 1. enum sub array, and find its min
// 1.1. 暴力,n**2, 1e10超时
// 1.2. dc,最坏情况下,1e10,又根据题意无法randomize,所以也超时了
//
// 2. enum min, and find sub array
// every num can be the min of some sub arrays, at least for the single element array
// enum every num as min, expand from both sides
// for the those sub arrays whose min is fixed
// only the longest is meaningful, because those shorters' sum are smaller
// and its sum-min product will never be anwser
// !!! so we enum every num as min, and expand from boths sides
// and record the answer only when both boundary are found!!!