子数组最小乘积的最大值

2021-05-09

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

难度中等6收藏分享切换为英文接收动态反馈

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

比方说，数组 [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

超时解法


public class Solution {
    public int maxSumMinProduct(int[] nums) {
        long result = 0;
        int len = nums.length;
        for(int i = 0; i < len; i++){
            // 用nums[i]作为子数组最小的元素,则向左向右构造一个子数组，使得子数组内每个元素都不小于nums[i]
            // 因为我们已经选定了最小的元素，所以子数组内的元素越多越好，越多和就越大，则乘积越大
            if(i != 0 && nums[i] == nums[i-1]){continue;}//去掉相邻重复的（已经用过了）
            long sum = 0;
            int j = i;
            while(j < len && nums[j] >= nums[i]){//向右寻找不小于它的数
                sum += nums[j];
                j++;
            }
            j = i-1;
            while(j >= 0 && nums[j] >= nums[i]){//向左寻找不小于它的数
                sum += nums[j];
                j--;
            }
            result = Math.max(result, nums[i]*sum);
        }
        return (int)(result%1000000007);
    }
}


作者：ji-bo-lai-zi-xing-xing-de
链接：https://leetcode-cn.com/problems/maximum-subarray-min-product/solution/java-gu-ding-zui-xiao-yuan-su-kuo-zhang-octq4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

前缀和+单调栈

class Solution {
public int maxSumMinProduct(int[] nums) {
        long[] prefixNums = new long[nums.length];
    	// 计算前缀和
        prefixNums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixNums[i] = prefixNums[i - 1] + nums[i];
        }

        Deque<Integer> upStack = new LinkedList<>();
        long max = 0;
        // 数组元素 下标 单调递增栈
    
    	// upStack是单调递增的栈
        for (int i = 0; i < nums.length; i++) {
            // 如果栈顶元素小于当前的元素,当前的元素入栈
            // 否则栈顶元素出栈,并记录目前的最大值,直到栈顶元素小于等于当前的元素,将目前的元素入栈
            if (upStack.isEmpty() || nums[upStack.peek()] <= nums[i]) {
                upStack.push(i);
            } else {
                // 每次出栈计算乘积
                // 如果不满足元素递增......
                while (!upStack.isEmpty() && nums[upStack.peek()] > nums[i]) {
                    // 当前栈顶的元素是最小值(为什么?)
                    int minIndex = upStack.pop();
                    // 栈顶的元素的index+1是子数组开始的index，这里为什么要+1？？？
                    int start = upStack.isEmpty() ? 0 : upStack.peek() + 1;
                    int end = i - 1;
                    max = Math.max(max, calcu(prefixNums, start, end, nums[minIndex]));
                }
                upStack.push(i);
            }
        }
        // 栈中剩余元素依次出栈，并计算乘积
        while (!upStack.isEmpty()) {
            int minIndex = upStack.pop();
            int end = nums.length - 1;
            int start = upStack.isEmpty() ? 0 : upStack.peek()+1;
            max = Math.max(max, calcu(prefixNums, start, end, nums[minIndex]));
        }
        return (int) (max % 1000000007);
    }

    // 求乘积
    private long calcu(long[] prefixNums, int start, int end, int min) {
        long sum = start == 0 ?
                prefixNums[end] :
                prefixNums[end] - prefixNums[start-1];
        return sum * min;
    }

}

参考文献

JAVA单调栈+前缀和 - 子数组最小乘积的最大值 - 力扣（LeetCode） (leetcode-cn.com)