Scale Engineer

Maximum Subarray Min-Product

Med
#1695Time: 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.
Patterns
Prefix Sum
Data structures
ArrayStackMonotonic Stack

Prompt

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

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 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.

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.

Solutions

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);  }}

Video 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.

← Previous

Previous problem

Next →

Next problem