Maximum Subarray Min-Product
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach considers every possible non-empty subarray. We can iterate through all possible start and end points of a subarray. For each subarray, we calculate its sum and find its minimum element to compute the min-product. A naive implementation would take O(n^3), but we can optimize it to O(n^2).
Algorithm
- Initialize a 64-bit integer
maxProductto 0. - Iterate through the array with an index
ifrom 0 ton-1to select the start of the subarray. - Inside this loop, initialize
currentSum = 0andminVal = Integer.MAX_VALUE. - Start a second loop with an index
jfromiton-1to select the end of the subarray. - In the inner loop, add
nums[j]tocurrentSumand updateminVal = min(minVal, nums[j]). This effectively considers the subarraynums[i...j]. - Calculate the current min-product:
(long)minVal * currentSum. - Update
maxProduct = max(maxProduct, current min-product). - After the loops complete, return
maxProductmodulo 10^9 + 7.
Walkthrough
We use two nested loops. The outer loop fixes the starting index i of the subarray. The inner loop iterates from i to the end of the array, effectively defining the subarray nums[i...j]. For each of these subarrays, we find the minimum value and the sum, calculate the min-product, and update the overall maximum. By updating the sum and minimum incrementally within the inner loop, we achieve an O(n^2) complexity.
class Solution { public int maxSumMinProduct(int[] nums) { int n = nums.length; long maxProduct = 0; final int MOD = 1_000_000_007; for (int i = 0; i < n; i++) { long currentSum = 0; int minVal = Integer.MAX_VALUE; for (int j = i; j < n; j++) { // Extend subarray nums[i...j-1] to nums[i...j] currentSum += nums[j]; minVal = Math.min(minVal, nums[j]); maxProduct = Math.max(maxProduct, minVal * currentSum); } } return (int) (maxProduct % MOD); }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. We have two nested loops iterating through the array.
Space
O(1), as we only use a few variables to store the running sum, minimum, and maximum product.
Trade-offs
Pros
Conceptually simple and easy to implement.
Requires minimal extra space.
Cons
The O(n^2) time complexity is too slow for the given constraints (n <= 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
A much more efficient approach is to change our perspective. Instead of iterating through all subarrays, we can iterate through each element nums[i] and treat it as the minimum element of a potential subarray. For each nums[i], we then find the largest possible subarray that contains nums[i] and has nums[i] as its minimum value. The min-product for this specific choice of minimum is nums[i] multiplied by the sum of this largest subarray. The maximum of these products over all i will be our answer.
Algorithm
- Create a prefix sum array
prefixSumof sizen+1, whereprefixSum[i]stores the sum of the firstielements. Note thatprefixSumshould be of typelongto avoid overflow. - Create an array
prevSmallerof sizen. Use a monotonic (increasing) stack to find the index of the first element to the left ofithat is strictly smaller thannums[i]. Store this index inprevSmaller[i]. If no such element exists, store -1. - Create an array
nextSmallerof sizen. Use a similar monotonic stack approach, iterating from right to left, to find the index of the first element to the right ofithat is strictly smaller thannums[i]. Store this innextSmaller[i]. If none exists, storen. - Initialize a 64-bit integer
maxProductto 0. - Iterate from
i = 0ton-1:- Get the left boundary index
L = prevSmaller[i]and right boundary indexR = nextSmaller[i]. - The subarray for which
nums[i]is the minimum isnums[L+1 ... R-1]. - Calculate the sum of this subarray using the prefix sum array:
sum = prefixSum[R] - prefixSum[L+1]. - Calculate the product:
product = (long)nums[i] * sum. - Update
maxProduct = max(maxProduct, product).
- Get the left boundary index
- Return
maxProductmodulo 10^9 + 7.
Walkthrough
To implement this, we need two key components:
- Finding Subarray Boundaries: For each
nums[i], the subarray where it's the minimum is bounded by the first element to its left that is strictly smaller thannums[i]and the first element to its right that is strictly smaller thannums[i]. This is a classic problem that can be solved efficiently in O(n) time using a monotonic stack. We can make two passes: one from left-to-right to find the 'previous smaller element' for each index, and another from right-to-left for the 'next smaller element'. - Calculating Subarray Sum: To quickly find the sum of any subarray
nums[L...R], we can pre-calculate a prefix sum array. With a prefix sum arrayP, the sum ofnums[L...R]can be found in O(1) time asP[R+1] - P[L].
By combining these techniques, we can solve the problem in linear time.
import java.util.Stack; class Solution { public int maxSumMinProduct(int[] nums) { int n = nums.length; int MOD = 1_000_000_007; // 1. Calculate prefix sums long[] prefixSum = new long[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } // 2. Find previous smaller element for each element int[] prevSmaller = new int[n]; Stack<Integer> stack = new Stack<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) { stack.pop(); } prevSmaller[i] = stack.isEmpty() ? -1 : stack.peek(); stack.push(i); } // 3. Find next smaller element for each element int[] nextSmaller = new int[n]; stack.clear(); for (int i = n - 1; i >= 0; i--) { while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) { stack.pop(); } nextSmaller[i] = stack.isEmpty() ? n : stack.peek(); stack.push(i); } // 4. Calculate max min-product long maxProduct = 0; for (int i = 0; i < n; i++) { int leftBoundaryIdx = prevSmaller[i]; int rightBoundaryIdx = nextSmaller[i]; // Subarray sum from index (leftBoundaryIdx + 1) to (rightBoundaryIdx - 1) long sum = prefixSum[rightBoundaryIdx] - prefixSum[leftBoundaryIdx + 1]; maxProduct = Math.max(maxProduct, nums[i] * sum); } return (int)(maxProduct % MOD); }}Complexity
Time
O(n). Calculating prefix sums is O(n). Finding previous and next smaller elements each take O(n). The final loop is also O(n). The total complexity is linear.
Space
O(n). We need O(n) space for the prefix sum array, O(n) for `prevSmaller`, O(n) for `nextSmaller`, and O(n) for the stack in the worst-case scenario.
Trade-offs
Pros
Optimal time complexity of O(n), which passes the given constraints.
Solves a general pattern of problems involving finding ranges defined by nearest smaller/greater elements.
Cons
More complex to understand and implement correctly.
Requires O(n) additional space for helper arrays and the stack.
Solutions
Solution
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)1 e9 + 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)) % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.