一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。
比方说,数组 [3,2,5] (最小值是 2)的最小乘积为 2 * (3+2+5) = 2 * 10 = 20
。
给你一个正整数数组 nums ,请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大,请你返回答案对 10^9 + 7 取余 的结果。
请注意,最小乘积的最大值考虑的是取余操作 之前 的结果。 题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。
子数组 定义为一个数组的 连续 部分。
示例 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
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-subarray-min-product 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
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);
}
};
280 ms 88 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!