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 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] × (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.
PythonJavaC++GoTypeScript
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(code-box)
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);
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
function maxSumMinProduct(nums: number[]): number {
const n = nums.length;
const left: number[] = Array(n).fill(-1);
const right: number[] = Array(n).fill(n);
const stk: number[] = [];
for (let i = 0; i < n; ++i) {
while (stk.length && nums[stk.at(-1)!] >= nums[i]) {
stk.pop();
}
if (stk.length) {
left[i] = stk.at(-1)!;
}
stk.push(i);
}
stk.length = 0;
for (let i = n - 1; i >= 0; --i) {
while (stk.length && nums[stk.at(-1)!] > nums[i]) {
stk.pop();
}
if (stk.length) {
right[i] = stk.at(-1)!;
}
stk.push(i);
}
const s: number[] = 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));
}(code-box)
