Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1856.html
1856. Maximum Subarray Min-Product
Level
Medium
Description
The min-product of an array is equal to the minimum value in the array multiplied by the array’s sum.
- For example, the array [3,2,5] (minimum value is 2) has a min-product of 2 * (3+2+5) = 2 * 10 = 20.
Given an array of integers nums
, return the maximum min-product of any non-empty subarray of nums
. Since the answer may be large, return it modulo 10^9 + 7
.
Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,2,3,2]
Output: 14
Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2).
2 * (2+3+2) = 2 * 7 = 14.
Example 2:
Input: nums = [2,3,3,1,2]
Output: 18
Explanation: The maximum min-product is achieved with the subarray [3,3] (minimum value is 3).
3 * (3+3) = 3 * 6 = 18.
Example 3:
Input: nums = [3,1,5,6,4,2]
Output: 60
Explanation: The maximum min-product is achieved with the subarray [5,6,4] (minimum value is 4).
4 * (5+6+4) = 4 * 15 = 60.
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^7
Solution
First, calculate the prefix sums of nums
, which can be used to calculate range sums effectively.
Then, use monotonic stack to find the left boundary and the right boundary of each nums[i]
. That is, left[i]
is the rightmost index such that left[i] < i
and nums[left[i]] > nums[i]
, and right[i]
is the leftmost index such that right[i] > i
and nums[right[i]] > nums[i]
. Then for each 0 <= i < nums.length
, the product that has nums[i]
as the minimum value is the range sum from left[i] + 1
to right[i] - 1
multiplied by nums[i]
. Loop over i
from 0 to nums.length - 1
to obtain the maximum subarray min-product.
-
class Solution { public int maxSumMinProduct(int[] nums) { final int MODULO = 1000000007; int length = nums.length; long[] prefixSums = new long[length + 1]; for (int i = 0; i < length; i++) prefixSums[i + 1] = prefixSums[i] + (long) nums[i]; int[] left = new int[length]; int[] right = new int[length]; Deque<Integer> stack = new LinkedList<Integer>(); for (int i = 0; i < length; i++) { while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) { stack.pop(); } left[i] = stack.isEmpty() ? -1 : stack.peek(); stack.push(i); } stack.clear(); for (int i = length - 1; i >= 0; i--) { while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) stack.pop(); right[i] = stack.isEmpty() ? length : stack.peek(); stack.push(i); } long maxProduct = 0; for (int i = 0; i < length; i++) { int leftIndex = left[i], rightIndex = right[i]; long rangeSum = getRangeSum(prefixSums, leftIndex + 1, rightIndex - 1); long product = rangeSum * (long) nums[i]; maxProduct = Math.max(maxProduct, product); } return (int) (maxProduct % MODULO); } public long getRangeSum(long[] prefixSums, int start, int end) { return prefixSums[end + 1] - prefixSums[start]; } }
-
Todo
-
class Solution: def maxSumMinProduct(self, nums: List[int]) -> int: mod = int(1e9) + 7 n = len(nums) left = [-1] * n right = [n] * n stk = [] for i, v in enumerate(nums): while stk and nums[stk[-1]] >= v: stk.pop() if stk: left[i] = stk[-1] stk.append(i) stk = [] for i in range(n - 1, -1, -1): while stk and nums[stk[-1]] > nums[i]: stk.pop() if stk: right[i] = stk[-1] stk.append(i) s = [0] + list(accumulate(nums)) ans = max(v * (s[right[i]] - s[left[i] + 1]) for i, v in enumerate(nums)) return ans % mod ############ # 1856. Maximum Subarray Min-Product # https://leetcode.com/problems/maximum-subarray-min-product class Solution: def maxSumMinProduct(self, nums: List[int]) -> int: M = 10 ** 9 + 7 n = len(nums) res = 0 prefix = [0] for x in nums: prefix.append(x + prefix[-1]) l = [0] * n r = [0] * n stack = [] for i in range(n): while stack and nums[stack[-1]] >= nums[i]: stack.pop() if stack: l[i] = stack[-1] + 1 else: l[i] = 0 stack.append(i) stack = [] for i in reversed(range(n)): while stack and nums[stack[-1]] >= nums[i]: stack.pop() if stack: r[i] = stack[-1] - 1 else: r[i] = n - 1 stack.append(i) for i in range(n): res = max(res, nums[i] * (prefix[r[i] + 1] - prefix[l[i]])) return res % M