Problem
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 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.
Examples
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.
Solution
Here we care about the max product and not the max width of the subarray, so sliding window is out of picture. Good solution is using Monotonic Stack.
Method 1 - Brute Force
Calculate subarray using nested loops, from i...j and calculate min-product.
If we calculate min product each time, time complexity of O(n^3)
But if each time we add element to subarray, we calculate min and update sum. This gives us O(n^2) solution.
Method 2 - Using Monotonic Stack and Prefix Sum
For each min product of subarray, we need min element in subarray and sum of all element. We can quickly know the sum of an subarray with prefix sum array. The difficult point is how to get the min value for each array very quickly.
If we use Segment Tree, but this still O(N^2), since you will find for each pair of [i, j]. So, that is out of picture.
We can focus on each number in nums, let it be the min and we expand from this number to right and to left. We want to ask what is the first number on the right that is smaller than this number, and what is the first number on the left that is smaller than this number
Here is the approach:
- Prefix Sum:
- Use a prefix sum array to efficiently calculate the sum of any subarray.
- Monotonic Stack:
- Use a monotonic stack to find the nearest smaller elements to the left and right of each element.
- This helps in identifying the subarray where the current element is the minimum.
- Calculate Min-Product:
- For each element, consider it as the minimum of a subarray.
- Use the prefix sum array to quickly calculate the sum of this subarray.
- Calculate the min-product and keep track of the maximum min-product found.
Code
Java
public class Solution {
public int maxSumMinProduct(int[] nums) {
int n = nums.length;
long[] prefixSum = new long[n + 1];
long mod = 1_000_000_007;
// Build prefix sum array
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
// Arrays to store the nearest smaller elements to the left and right
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(left, -1);
Arrays.fill(right, n);
Deque<Integer> stack = new ArrayDeque<>();
// Find nearest smaller to the left
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
stack.pop();
}
if (!stack.isEmpty()) {
left[i] = stack.peek();
}
stack.push(i);
}
stack.clear();
// Find nearest smaller to the right
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
stack.pop();
}
if (!stack.isEmpty()) {
right[i] = stack.peek();
}
stack.push(i);
}
// Calculate the maximum min-product
long maxMinProduct = 0;
for (int i = 0; i < n; i++) {
int l = left[i] + 1;
int r = right[i] - 1;
long sum = prefixSum[r + 1] - prefixSum[l];
long minProduct = sum * nums[i];
maxMinProduct = Math.max(maxMinProduct, minProduct);
}
return (int)(maxMinProduct % mod);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums1 = {1, 2, 3, 2};
System.out.println(sol.maxSumMinProduct(nums1)); // Expected output: 14
int[] nums2 = {2, 3, 3, 1, 2};
System.out.println(sol.maxSumMinProduct(nums2)); // Expected output: 18
}
}
Python
class Solution:
def maxSumMinProduct(self, nums: List[int]) -> int:
n = len(nums)
mod = 10**9 + 7
# Build prefix sum array
prefix_sum = [0] * (n + 1)
for i in range(n):
prefix_sum[i + 1] = prefix_sum[i] + nums[i]
# Arrays to store the nearest smaller elements to the left and right
left = [-1] * n
right = [n] * n
# Find nearest smaller to the left
stack = []
for i in range(n):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if stack:
left[i] = stack[-1]
stack.append(i)
# Find nearest smaller to the right
stack = []
for i in range(n-1, -1, -1):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if stack:
right[i] = stack[-1]
stack.append(i)
# Calculate the maximum min-product
max_min_product = 0
for i in range(n):
l = left[i] + 1
r = right[i] - 1
total = prefix_sum[r + 1] - prefix_sum[l]
min_product = total * nums[i]
max_min_product = max(max_min_product, min_product)
return max_min_product % mod
Complexity
- ⏰ Time complexity:
O(n), wherenis the number of elements in the array. This is because we traverse the array a constant number of times to build the prefix sum, find the nearest smaller elements, and calculate the min-product. - 🧺 Space complexity:
O(n), for storing the prefix sum array and stacks.