Maximum Subarray Min-Product — Problem & Solution
Maximum Subarray Min-Product solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Subarray Min-Product is a medium coding problem on arrays, prefix sum and stack, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Prefix Sum, Stack, Monotonic Stack
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The min-product of an array is its minimum value multiplied by its sum; for example [3,2,5] has min-product 2 × (3 + 2 + 5) = 20.
Given an array nums of positive integers, find the largest min-product over all of its non-empty subarrays. Compare the exact products; only the final maximum is reduced, and you return it modulo 10^9 + 7.
(The value bound below is tighter than the original problem's so that the exact maximum stays below 2^53.)
Example 1
Input: nums = [3,1,4,4,2]
Output: 32
Explanation: `[4,4]` gives 4 × 8 = 32.
Example 2
Input: nums = [2,5,4,1,3]
Output: 36
Explanation: `[5,4]` gives 4 × 9 = 36.
Example 3
Input: nums = [100000,100000]
Output: 999999867
Explanation: The whole array gives 100000 × 200000 = 2 · 10^10, which is 999999867 modulo 10^9 + 7.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^5
Hints for Maximum Subarray Min-Product
Hint 1
Fix which element is the minimum. Since every value is positive, how far should the subarray extend around it?
Hint 2
Around index
i, extend left and right as long as the values are at leastnums[i]— a longer subarray with the same minimum has a larger sum.Hint 3
Find those borders for every index with a monotonic stack (previous and next strictly smaller element) and read the sums from a prefix-sum array.
How to solve Maximum Subarray Min-Product
For each index treated as the minimum, the best subarray is the widest one in which it stays the minimum. A monotonic stack finds every such window in linear time and a prefix sum prices it.
Approach
- Build prefix sums
P(as 64-bit integers — sums reach 10^10). - With a monotonic stack find
L[i], the previous index with a smaller value (or -1), andR[i], the next index with a smaller-or-equal value (orn). - Candidate for
i:nums[i] × (P[R[i]] - P[L[i] + 1]). Track the maximum. - Return the maximum modulo
10^9 + 7.
Why it works
Take an optimal subarray and its minimum m. Because all values are positive, extending it over neighbours >= m keeps the minimum and grows the sum, so some optimal subarray is a maximal run of values >= m. The rightmost index holding m in that run has exactly that run as its window (strictly smaller to the left boundary, smaller-or-equal to the right one), so its candidate equals the optimum.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Take the maximum before the modulus — comparing reduced values picks the wrong subarray.
- Sums overflow 32 bits; keep prefix sums and products in 64-bit.
- Ties need no special care for a maximum: the rightmost copy of the minimum in a run sees the whole run, so stopping at equal values on the right loses nothing.
Reference solution
Python
from typing import List
def maxSumMinProduct(nums: List[int]) -> int:
n = len(nums)
prefix = [0] * (n + 1)
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
left = [-1] * n
right = [n] * n
st = []
for i in range(n):
while st and nums[st[-1]] >= nums[i]:
right[st.pop()] = i
left[i] = st[-1] if st else -1
st.append(i)
best = 0
for i in range(n):
best = max(best, nums[i] * (prefix[right[i]] - prefix[left[i] + 1]))
return best % (10**9 + 7)Java
public static int maxSumMinProduct(int[] nums) {
int n = nums.length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
int[] left = new int[n], right = new int[n], st = new int[n];
int top = 0;
for (int i = 0; i < n; i++) {
right[i] = n;
while (top > 0 && nums[st[top - 1]] >= nums[i]) right[st[--top]] = i;
left[i] = top > 0 ? st[top - 1] : -1;
st[top++] = i;
}
long best = 0;
for (int i = 0; i < n; i++) {
best = Math.max(best, nums[i] * (prefix[right[i]] - prefix[left[i] + 1]));
}
return (int) (best % 1000000007L);
}C++
int maxSumMinProduct(vector<int>& nums) {
int n = nums.size();
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
vector<int> left(n, -1), right(n, n), st;
for (int i = 0; i < n; i++) {
while (!st.empty() && nums[st.back()] >= nums[i]) {
right[st.back()] = i;
st.pop_back();
}
left[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
long long best = 0;
for (int i = 0; i < n; i++) {
best = max(best, (long long)nums[i] * (prefix[right[i]] - prefix[left[i] + 1]));
}
return (int)(best % 1000000007LL);
}JavaScript
var maxSumMinProduct = function(nums) {
var n = nums.length;
var prefix = new Array(n + 1).fill(0);
for (var i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
var left = new Array(n), right = new Array(n).fill(n), st = [];
for (var j = 0; j < n; j++) {
while (st.length > 0 && nums[st[st.length - 1]] >= nums[j]) right[st.pop()] = j;
left[j] = st.length > 0 ? st[st.length - 1] : -1;
st.push(j);
}
var best = 0;
for (var k = 0; k < n; k++) {
var cand = nums[k] * (prefix[right[k]] - prefix[left[k] + 1]);
if (cand > best) best = cand;
}
return best % 1000000007;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum