一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。
- 比方说，数组
[3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。
给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对 109 + 7 取余 的结果。
请注意，最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。
子数组 定义为一个数组的 连续 部分。
示例 1：
1
2
3
4
| 输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14 。
|
示例 2：
1
2
3
4
| 输入：nums = [2,3,3,1,2]
输出：18
解释：最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。
3 * (3+3) = 3 * 6 = 18 。
|
示例 3：
1
2
3
4
| 输入：nums = [3,1,5,6,4,2]
输出：60
解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。
4 * (5+6+4) = 4 * 15 = 60 。
|
提示：
1 <= nums.length <= 1051 <= nums[i] <= 107
思路：
枚举数组中每个值 n ，并且以 n 作为子数组中的最小值，再乘以这个子数组的和。
C++代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
private:
typedef long long ll;
const int mod = 1e9+7;
public:
int maxSumMinProduct(vector<int>& nums) {
int n = nums.size();
vector<ll> pre(n + 1);
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + nums[i - 1];
}
stack<int> s;
vector<int> left(n, 0);
vector<int> right(n, n - 1);
for (int i = 0; i < n; i++) {
while (!s.empty() && nums[i] < nums[s.top()]) {
right[s.top()] = i - 1;
s.pop();
}
if (!s.empty()) {
left[i] = s.top() + 1;
}
s.push(i);
}
ll ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, (pre[right[i] + 1] - pre[left[i]]) * nums[i]);
}
return ans % mod;
}
};
|
