题目描述

一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。
比方说，数组 [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

题解

  • 以元素i作为子数组的最小值，则确定子数组的左右边界即可。子数组即左右小于元素i的最近元素构成的开区间。
  • 子数组的边界通过两个单调栈计算。
  • 子数组的和通过前缀和计算。
    class Solution {
  public int maxSumMinProduct(int[] nums) {
      long max = 0;
      Stack<Integer> stack = new Stack<>();
      int[] left = new int[nums.length];
      // 以nums[i]作为最小元素的子数组的左边界
      for (int i = 0; i < nums.length; ++i) {
          while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
              stack.pop();
          }
          if (stack.isEmpty()) {
              left[i] = 0;
          } else {
              left[i] = stack.peek() + 1;
          }
          stack.push(i);
      }
      int[] right = new int[nums.length];
      right[nums.length - 1] = nums.length - 1;
      stack.clear();
      // 以nums[i]作为最小元素的子数组的右边界
      for (int i = nums.length - 1; i >= 0; --i) {
          while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
              stack.pop();
          }
          if (stack.isEmpty()) {
              right[i] = nums.length - 1;
          } else {
              right[i] = stack.peek() - 1;
          }
          stack.push(i);
      }
      long[] sum = new long[nums.length];
      sum[0] = nums[0];
      // 前缀和
      for (int i = 1; i < nums.length; ++i) {
          sum[i] = nums[i] + sum[i - 1];
      }
      for (int i = 0; i < nums.length; ++i) {
          long temp = 0;
          if (left[i] == right[i]) {
              temp = nums[i] * nums[i];
          } else {
              temp = nums[i] * (sum[right[i]] - sum[left[i]] + nums[left[i]]);
          }
          if (max < temp) {
              max = temp;
          }
      }
      return (int)(max%1000000007);
  }
}

注：单调栈可用于统计数组中元素的变化拐点(极值点）。