class Solution {
public:
int maxSumMinProduct(vector<int>& nums) {
}
};
1856. 子数组最小乘积的最大值
一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。
[3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对 109 + 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 <= 1051 <= nums[i] <= 107原站题解
java 解法, 执行用时: 43 ms, 内存消耗: 53.6 MB, 提交时间: 2023-09-18 14:46:19
public class Solution {
public int maxSumMinProduct(int[] nums) {
int len = nums.length;
int[] left = new int[len];
int[] right = new int[len];
Deque<Integer> stack = new LinkedList<>();
// 对于每一个i 找到右侧连续的不小于它的元素，记录最后一个连续的，不小于它的元素对应下标
for(int i = 0; i < len; i++){
while(!stack.isEmpty() && nums[stack.peek()] > nums[i]){right[stack.pop()] = i-1;}
stack.push(i);//存放的是下标
}
while(!stack.isEmpty()){right[stack.pop()] = len-1;}
// 对于每一个i 找到左侧连续的不小于它的元素，记录最后一个连续的，不小于它的元素对应下标
for(int i = len-1; i >= 0; i--){
while(!stack.isEmpty() && nums[stack.peek()] > nums[i]){left[stack.pop()] = i+1;}
stack.push(i);//存放的是下标
}
while(!stack.isEmpty()){left[stack.pop()] = 0;}
//前缀和,用long来存放，防止相加时溢出
long[] dp = new long[len];
dp[0] = nums[0];
for(int i = 1; i < len; i++){dp[i] = dp[i-1] + nums[i];}
long result = 0;
for(int i = 0; i < len; i++){
result = Math.max(result, nums[i]*(dp[right[i]]-dp[left[i]]+nums[left[i]]));
}//right[i]为右坐标 left[i]为左坐标，从left[i]到right[i]所有元素的和应该是dp[right[i]]-dp[left[i]]+nums[left[i]]
return (int)(result%1000000007);
}
}
cpp 解法, 执行用时: 208 ms, 内存消耗: 88.1 MB, 提交时间: 2023-09-18 14:45:58
class Solution {
private:
using LL = long long;
static constexpr int mod = 1000000007;
public:
int maxSumMinProduct(vector<int>& nums) {
int n = nums.size();
// 数组 left 初始化为 0，数组 right 初始化为 n-1
// 设置为元素不存在时的特殊值
vector<int> left(n), right(n, n - 1);
// 单调栈
stack<int> s;
for (int i = 0; i < n; ++i) {
while (!s.empty() && nums[s.top()] >= nums[i]) {
// 这里的 right 是非严格定义的，right[i] 是右侧最近的小于等于 nums[i] 的元素下标
right[s.top()] = i - 1;
s.pop();
}
if (!s.empty()) {
// 这里的 left 是严格定义的，left[i] 是左侧最近的严格小于 nums[i] 的元素下标
left[i] = s.top() + 1;
}
s.push(i);
}
// 前缀和
vector<LL> pre(n + 1);
for (int i = 1; i <= n; ++i) {
pre[i] = pre[i - 1] + nums[i - 1];
}
LL best = 0;
for (int i = 0; i < n; ++i) {
best = max(best, (pre[right[i] + 1] - pre[left[i]]) * nums[i]);
}
return best % mod;
}
};
python3 解法, 执行用时: 428 ms, 内存消耗: 36.7 MB, 提交时间: 2023-09-18 14:45:49
class Solution:
def maxSumMinProduct(self, nums: List[int]) -> int:
mod = 10**9 + 7
n = len(nums)
# 数组 left 初始化为 0，数组 right 初始化为 n-1
# 设置为元素不存在时的特殊值
left, right = [0] * n, [n - 1] * n
# 单调栈
s = list()
for i, num in enumerate(nums):
while s and nums[s[-1]] >= num:
# 这里的 right 是非严格定义的，right[i] 是右侧最近的小于等于 nums[i] 的元素下标
right[s[-1]] = i - 1
s.pop()
if s:
# 这里的 left 是严格定义的，left[i] 是左侧最近的严格小于 nums[i] 的元素下标
left[i] = s[-1] + 1
s.append(i)
# 前缀和
pre = [0]
for i, num in enumerate(nums):
pre.append(pre[-1] + num)
best = max((pre[right[i] + 1] - pre[left[i]]) * num for i, num in enumerate(nums))
return best % mod
golang 解法, 执行用时: 132 ms, 内存消耗: 9.5 MB, 提交时间: 2023-09-18 14:43:23
// 单调栈+前缀和
func maxSumMinProduct(a []int) (ans int) {
type pair struct{ v, i int }
n := len(a)
sum := make([]int, n+1)
posL := make([]int, n)
stk := []pair{{0, -1}}
for i, v := range a {
sum[i+1] = sum[i] + v
for {
if top := stk[len(stk)-1]; top.v < v {
posL[i] = top.i
break
}
stk = stk[:len(stk)-1]
}
stk = append(stk, pair{v, i})
}
posR := make([]int, n)
stk = []pair{{0, n}}
for i := n - 1; i >= 0; i-- {
v := a[i]
for {
if top := stk[len(stk)-1]; top.v < v {
posR[i] = top.i
break
}
stk = stk[:len(stk)-1]
}
stk = append(stk, pair{v, i})
}
for i, v := range a {
ans = max(ans, v*(sum[posR[i]]-sum[posL[i]+1]))
}
return ans % (1e9 + 7)
}
func max(a, b int) int { if a > b { return a }; return b }