Range Minimum Query (RMQ)

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

Approach: Monotonic Stack with Prefix Sums

Algorithm

1. For every element nums[i], treat it as the minimum of a candidate subarray
2. Use a monotonic (strictly increasing) stack to find left[i], the first index to the left where the value is smaller than nums[i], and right[i], the first index to the right where the value is smaller than nums[i]
3. The largest subarray where nums[i] is the minimum spans exactly [left[i] + 1, right[i] - 1]
4. Build a prefix sum array so the sum of any such subarray is prefix[right[i]] - prefix[left[i] + 1]
5. Compute nums[i] * subarraySum for every index, keep the maximum, and return it modulo 10^9 + 7

Time & Space Complexity

• Time Complexity: O(n) - each index is pushed and popped from the stack once
• Space Complexity: O(n) - the stack, the prefix sums, and the boundary arrays

Java Implementation

import java.util.ArrayDeque;
import java.util.Deque;

public class MaximumSubarrayMinProduct {

    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        long MOD = 1_000_000_007L;

        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];
        int[] right = new int[n];

        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? 0 : stack.peek() + 1;
            stack.push(i);
        }

        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n - 1 : stack.peek() - 1;
            stack.push(i);
        }

        long max = 0;
        for (int i = 0; i < n; i++) {
            long sum = prefix[right[i] + 1] - prefix[left[i]];
            max = Math.max(max, nums[i] * sum);
        }

        return (int) (max % MOD);
    }

    // Test method
    public static void main(String[] args) {
        MaximumSubarrayMinProduct solver = new MaximumSubarrayMinProduct();
        int[] nums1 = {1, 2, 3, 2};
        System.out.println("maxSumMinProduct([1,2,3,2]): " + solver.maxSumMinProduct(nums1)); // Expected: 14

        int[] nums2 = {2, 3, 3, 1, 2};
        System.out.println("maxSumMinProduct([2,3,3,1,2]): " + solver.maxSumMinProduct(nums2)); // Expected: 18

        int[] nums3 = {3, 1, 5, 6, 4, 2};
        System.out.println("maxSumMinProduct([3,1,5,6,4,2]): " + solver.maxSumMinProduct(nums3)); // Expected: 60
    }
}

Example Walkthrough

For nums = [1, 2, 3, 2]:

1. Boundaries: index 2 (value 3) spans [2,2] (sum 3, min 3), index 3 (value 2) spans [1,3] (sum 7, min 2)
2. Candidate for nums[1]=2: left[1]=0, right[1]=3, sum = 1+2+3+2 = 8, product = 16
3. Candidate for nums[2]=3: left[2]=2, right[2]=2, sum = 3, product = 9
4. Candidate for nums[3]=2: left[3]=1, right[3]=3, sum = 2+3+2 = 7, product = 14
5. Maximum is 14, achieved by subarray [2,3,2]

Key Points

1. Range Minimum Query Idea: The monotonic stack answers, for each element, the maximal range in which it is the minimum — a classic RMQ-style boundary problem
2. >= in the stack condition: Using >= guarantees ties choose the leftmost minimum and keeps the range computation correct
3. Prefix Sums: Subarray sums are answered in O(1) after an O(n) prefix build
4. Overflow Safety: Use long for sums and products since values can be large, and only reduce mod at the end
5. O(n): Each element enters and leaves the stack exactly once, unlike the O(n²) brute force over all subarrays