# Maximum Subarray Min-Product **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximum-subarray-min-product) Canonical: https://scaleengineer.com/dsa/problems/maximum-subarray-min-product **Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum) **Data structures:** Array, Stack, Monotonic Stack --- ## 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 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 <= 105` * `1 <= nums[i] <= 107` # Approaches ## Brute Force with Optimization 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). **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. **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. ### Explanation 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. ```java 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); } } ``` ### Algorithm - Initialize a 64-bit integer `maxProduct` to 0. - Iterate through the array with an index `i` from 0 to `n-1` to select the start of the subarray. - Inside this loop, initialize `currentSum = 0` and `minVal = Integer.MAX_VALUE`. - Start a second loop with an index `j` from `i` to `n-1` to select the end of the subarray. - In the inner loop, add `nums[j]` to `currentSum` and update `minVal = min(minVal, nums[j])`. This effectively considers the subarray `nums[i...j]`. - Calculate the current min-product: `(long)minVal * currentSum`. - Update `maxProduct = max(maxProduct, current min-product)`. - After the loops complete, return `maxProduct` modulo 10^9 + 7. ## Monotonic Stack with Prefix Sum 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. **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. **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. ### Explanation To implement this, we need two key components: 1. **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 than `nums[i]` and the first element to its right that is strictly smaller than `nums[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'. 2. **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 array `P`, the sum of `nums[L...R]` can be found in O(1) time as `P[R+1] - P[L]`. By combining these techniques, we can solve the problem in linear time. ```java 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 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); } } ``` ### Algorithm - Create a prefix sum array `prefixSum` of size `n+1`, where `prefixSum[i]` stores the sum of the first `i` elements. Note that `prefixSum` should be of type `long` to avoid overflow. - Create an array `prevSmaller` of size `n`. Use a monotonic (increasing) stack to find the index of the first element to the left of `i` that is strictly smaller than `nums[i]`. Store this index in `prevSmaller[i]`. If no such element exists, store -1. - Create an array `nextSmaller` of size `n`. Use a similar monotonic stack approach, iterating from right to left, to find the index of the first element to the right of `i` that is strictly smaller than `nums[i]`. Store this in `nextSmaller[i]`. If none exists, store `n`. - Initialize a 64-bit integer `maxProduct` to 0. - Iterate from `i = 0` to `n-1`: - Get the left boundary index `L = prevSmaller[i]` and right boundary index `R = nextSmaller[i]`. - The subarray for which `nums[i]` is the minimum is `nums[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)`. - Return `maxProduct` modulo 10^9 + 7. # Solutions ### Java ```java 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 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); } } ``` ### CPP ```cpp class Solution { public: int maxSumMinProduct(vector &nums) { int n = nums.size(); vector left(n, -1); vector right(n, n); stack 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(); 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; } }; ``` ### Python ```python 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 ```