README.md

1856. 子数组最小乘积的最大值

English Version

题目描述

一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。

• 比方说，数组 [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 <= 105
• 1 <= nums[i] <= 107

解法

“前缀和 + 单调栈”实现。

Python3

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        # 前缀和
        pre_sum = [0] * (n + 1)
        for i in range(1, n + 1):
            pre_sum[i] = pre_sum[i - 1] + nums[i - 1]

        # 单调栈求下一个较小值
        stack = []
        next_lesser = [n] * n
        for i in range(n):
            while stack and nums[stack[-1]] > nums[i]:
                next_lesser[stack.pop()] = i
            stack.append(i)

        # 单调栈求前一个较小值
        stack = []
        prev_lesser = [-1] * n
        for i in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] > nums[i]:
                prev_lesser[stack.pop()] = i
            stack.append(i)

        res = 0
        for i in range(n):
            start, end = prev_lesser[i], next_lesser[i]
            t = nums[i] * (pre_sum[end] - pre_sum[start + 1])
            res = max(res, t)
        return res % (10 ** 9 + 7)

Java

class Solution {
    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;

        // 前缀和
        long[] preSum = new long[n + 1];
        for (int i = 1; i < n + 1; ++i) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        // 单调栈求下一个较小值
        Deque<Integer> stack = new ArrayDeque<>();
        int[] nextLesser = new int[n];
        Arrays.fill(nextLesser, n);
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                nextLesser[stack.pop()] = i;
            }
            stack.push(i);
        }

        // 单调栈求前一个较小值
        stack = new ArrayDeque<>();
        int[] prevLesser = new int[n];
        Arrays.fill(prevLesser, -1);
        for (int i = n - 1; i >= 0; --i) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                prevLesser[stack.pop()] = i;
            }
            stack.push(i);
        }
        long res = 0;
        for (int i = 0; i < n; ++i) {
            int start = prevLesser[i], end = nextLesser[i];
            long t = nums[i] * (preSum[end] - preSum[start + 1]);
            res = Math.max(res, t);
        }
        return (int) (res % 1000000007);
    }
}

...