Welcome to Subscribe On Youtube
1856. Maximum Subarray Min-Product
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 is2) has a min-product of2 * (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 109 + 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 <= 1051 <= nums[i] <= 107
Solutions
Solution 1: Monotonic Stack + Prefix Sum
We can enumerate each element $nums[i]$ as the minimum value of the subarray, and find the left and right boundaries $left[i]$ and $right[i]$ of the subarray. Where $left[i]$ represents the first position strictly less than $nums[i]$ on the left side of $i$, and $right[i]$ represents the first position less than or equal to $nums[i]$ on the right side of $i$.
To conveniently calculate the sum of the subarray, we can preprocess the prefix sum array $s$, where $s[i]$ represents the sum of the first $i$ elements of $nums$.
Then the minimum product with $nums[i]$ as the minimum value of the subarray is $nums[i] \times (s[right[i]] - s[left[i] + 1])$. We can enumerate each element $nums[i]$, find the minimum product with $nums[i]$ as the minimum value of the subarray, and then take the maximum value.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array $nums$.
-
class Solution { public int maxSumMinProduct(int[] nums) { int n = nums.length; int[] left = new int[n]; int[] right = new int[n]; Arrays.fill(left, -1); Arrays.fill(right, n); Deque<Integer> stk = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) { stk.pop(); } if (!stk.isEmpty()) { left[i] = stk.peek(); } stk.push(i); } stk.clear(); for (int i = n - 1; i >= 0; --i) { while (!stk.isEmpty() && nums[stk.peek()] > nums[i]) { stk.pop(); } if (!stk.isEmpty()) { right[i] = stk.peek(); } stk.push(i); } long[] s = new long[n + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } long ans = 0; for (int i = 0; i < n; ++i) { ans = Math.max(ans, nums[i] * (s[right[i]] - s[left[i] + 1])); } final int mod = (int) 1e9 + 7; return (int) (ans % mod); } } -
class Solution { public: int maxSumMinProduct(vector<int>& nums) { int n = nums.size(); vector<int> left(n, -1); vector<int> right(n, n); stack<int> stk; for (int i = 0; i < n; ++i) { while (!stk.empty() && nums[stk.top()] >= nums[i]) { stk.pop(); } if (!stk.empty()) { left[i] = stk.top(); } stk.push(i); } stk = stack<int>(); for (int i = n - 1; ~i; --i) { while (!stk.empty() && nums[stk.top()] > nums[i]) { stk.pop(); } if (!stk.empty()) { right[i] = stk.top(); } stk.push(i); } long long s[n + 1]; s[0] = 0; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } long long ans = 0; for (int i = 0; i < n; ++i) { ans = max(ans, nums[i] * (s[right[i]] - s[left[i] + 1])); } const int mod = 1e9 + 7; return ans % mod; } }; -
class Solution: def maxSumMinProduct(self, nums: List[int]) -> int: n = len(nums) left = [-1] * n right = [n] * n stk = [] for i, x in enumerate(nums): while stk and nums[stk[-1]] >= x: 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 = list(accumulate(nums, initial=0)) mod = 10**9 + 7 return max((s[right[i]] - s[left[i] + 1]) * x for i, x in enumerate(nums)) % mod -
func maxSumMinProduct(nums []int) int { n := len(nums) left := make([]int, n) right := make([]int, n) for i := range left { left[i] = -1 right[i] = n } stk := []int{} for i, x := range nums { for len(stk) > 0 && nums[stk[len(stk)-1]] >= x { stk = stk[:len(stk)-1] } if len(stk) > 0 { left[i] = stk[len(stk)-1] } stk = append(stk, i) } stk = []int{} for i := n - 1; i >= 0; i-- { for len(stk) > 0 && nums[stk[len(stk)-1]] > nums[i] { stk = stk[:len(stk)-1] } if len(stk) > 0 { right[i] = stk[len(stk)-1] } stk = append(stk, i) } s := make([]int, n+1) for i, x := range nums { s[i+1] = s[i] + x } ans := 0 for i, x := range nums { if t := x * (s[right[i]] - s[left[i]+1]); ans < t { ans = t } } const mod = 1e9 + 7 return ans % mod } -
function maxSumMinProduct(nums: number[]): number { const n = nums.length; const left: number[] = new Array(n).fill(-1); const right: number[] = new Array(n).fill(n); let stk: number[] = []; for (let i = 0; i < n; ++i) { while (stk.length && nums[stk[stk.length - 1]] >= nums[i]) { stk.pop(); } if (stk.length) { left[i] = stk[stk.length - 1]; } stk.push(i); } stk = []; for (let i = n - 1; i >= 0; --i) { while (stk.length && nums[stk[stk.length - 1]] > nums[i]) { stk.pop(); } if (stk.length) { right[i] = stk[stk.length - 1]; } stk.push(i); } const s: number[] = new Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } let ans: bigint = 0n; const mod = 10 ** 9 + 7; for (let i = 0; i < n; ++i) { const t = BigInt(nums[i]) * BigInt(s[right[i]] - s[left[i] + 1]); if (ans < t) { ans = t; } } return Number(ans % BigInt(mod)); }