题目描述
一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和。
- 比方说,数组
[3,2,5]
(最小值是2
)的最小乘积为2 * (3+2+5) = 2 * 10 = 20
。
给你一个正整数数组 nums
,请你返回 nums
任意 非空子数组 的 最小乘积 的 最大值。由于答案可能很大,请你返回答案对 10^9 + 7
取余 的结果。
请注意,最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。
子数组 定义为一个数组的 连续 部分。
样例
输入:nums = [1,2,3,2]
输出:14
解释:最小乘积的最大值由子数组 [2,3,2] (最小值是 2)得到。
2 * (2+3+2) = 2 * 7 = 14。
输入:nums = [2,3,3,1,2]
输出:18
解释:最小乘积的最大值由子数组 [3,3] (最小值是 3)得到。
3 * (3+3) = 3 * 6 = 18。
输入: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
算法
(贪心,单调栈) $O(n)$
- 对于一个数字 $nums(i)$ 来说,以该数字为最小值的最大连续子数组为 $[l_i, r_i]$,则使用 $nums(i) \cdot \sum_{k=l_i}^{r_i} nums(k)$。
- 通过两次单调栈可以求出每个位置的 $l_i$ 和 $r_i$。
- 通过预处理前缀和,可以快速计算并更新答案。
时间复杂度
- 单调栈的时间复杂度为 $O(n)$。
- 更新答案的时间复杂度为 $O(n)$。
- 故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储单调栈和前缀和数组。
C++ 代码
#define LL long long
class Solution {
public:
int maxSumMinProduct(vector<int>& nums) {
const int mod = 1000000007;
const int n = nums.size();
stack<int> s;
vector<int> l(n), r(n);
for (int i = 0; i < n; i++) {
while (!s.empty() && nums[s.top()] > nums[i]) {
r[s.top()] = i - 1;
s.pop();
}
s.push(i);
}
while (!s.empty()) {
r[s.top()] = n - 1;
s.pop();
}
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && nums[s.top()] > nums[i]) {
l[s.top()] = i + 1;
s.pop();
}
s.push(i);
}
while (!s.empty()) {
l[s.top()] = 0;
s.pop();
}
vector<LL> sum(n);
sum[0] = nums[0];
for (int i = 1; i < n; i++)
sum[i] = sum[i - 1] + nums[i];
LL ans = 0;
for (int i = 0; i < n; i++) {
LL t = sum[r[i]];
if (l[i] > 0) t -= sum[l[i] - 1];
ans = max(ans, nums[i] * t);
}
return ans % mod;
}
};