Code Implementation

class Solution:
    def maxSumMinProduct(self, nums):
        n = len(nums)
        stack = []
        left = [0] * n
        right = [n - 1] * n

        # Find left boundary for each element
        for i in range(n):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            left[i] = stack[-1] + 1 if stack else 0
            stack.append(i)

        stack = []
        # Find right boundary for each element
        for i in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            right[i] = stack[-1] - 1 if stack else n - 1
            stack.append(i)

        # Prefix sums
        prefix = [0]
        for num in nums:
            prefix.append(prefix[-1] + num)

        MOD = 10**9 + 7
        ans = 0
        for i in range(n):
            total = prefix[right[i] + 1] - prefix[left[i]]
            ans = max(ans, nums[i] * total)
        return ans % MOD
      

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n), right(n);
        stack<int> st;
        // Find left boundary
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && nums[st.top()] >= nums[i]) st.pop();
            left[i] = st.empty() ? 0 : st.top() + 1;
            st.push(i);
        }
        while (!st.empty()) st.pop();
        // Find right boundary
        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && nums[st.top()] >= nums[i]) st.pop();
            right[i] = st.empty() ? n - 1 : st.top() - 1;
            st.push(i);
        }
        // Prefix sums
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + nums[i];
        long long ans = 0, MOD = 1e9 + 7;
        for (int i = 0; i < n; ++i) {
            long long total = prefix[right[i] + 1] - prefix[left[i]];
            ans = max(ans, total * nums[i]);
        }
        return ans % MOD;
    }
};
      

class Solution {
    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        int[] left = new int[n], right = new int[n];
        Stack<Integer> stack = new Stack<>();
        // Find left boundary
        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();
        // Find right boundary
        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);
        }
        // Prefix sums
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + nums[i];
        long ans = 0, MOD = 1000000007;
        for (int i = 0; i < n; ++i) {
            long total = prefix[right[i] + 1] - prefix[left[i]];
            ans = Math.max(ans, total * nums[i]);
        }
        return (int)(ans % MOD);
    }
}
      

var maxSumMinProduct = function(nums) {
    const n = nums.length;
    let left = new Array(n).fill(0);
    let right = new Array(n).fill(n - 1);
    let stack = [];
    // Find left boundary
    for (let i = 0; i < n; ++i) {
        while (stack.length && nums[stack[stack.length - 1]] >= nums[i]) stack.pop();
        left[i] = stack.length ? stack[stack.length - 1] + 1 : 0;
        stack.push(i);
    }
    stack = [];
    // Find right boundary
    for (let i = n - 1; i >= 0; --i) {
        while (stack.length && nums[stack[stack.length - 1]] >= nums[i]) stack.pop();
        right[i] = stack.length ? stack[stack.length - 1] - 1 : n - 1;
        stack.push(i);
    }
    // Prefix sums
    let prefix = [0];
    for (let num of nums) prefix.push(prefix[prefix.length - 1] + num);
    let ans = 0, MOD = 1e9 + 7;
    for (let i = 0; i < n; ++i) {
        let total = prefix[right[i] + 1] - prefix[left[i]];
        ans = Math.max(ans, nums[i] * total);
    }
    return ans % MOD;
};
      

Problem Description

Given an array of positive integers nums, you are asked to find the maximum value of min-product across all non-empty subarrays of nums. The min-product of a subarray is defined as the minimum element in the subarray multiplied by the sum of all elements in that subarray.

Your task is to return the maximum min-product possible, modulo 109 + 7.

• You must consider all possible contiguous subarrays.
• Each subarray's min-product is min(subarray) * sum(subarray).
• Constraints:
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^7

Thought Process

At first glance, this problem seems to require checking every possible subarray, calculating both the minimum and sum for each, and then taking the maximum min-product. However, with up to 100,000 elements, a brute-force approach that checks all O(n^2) subarrays is infeasible.

The key insight is to realize that for each index, we can ask: for which subarrays is nums[i] the minimum? If we can efficiently find the largest subarray (to the left and right) where nums[i] remains the minimum, then nums[i] is the smallest in that range, and we can calculate the sum quickly using prefix sums.

We need a way to, for each position, find the boundaries to the left and right where a number is still the minimum. This is a classic problem solved by using a monotonic stack.

Solution Approach

The optimized solution combines three main techniques: monotonic stacks for boundaries, prefix sums for range sums, and a single pass to compute the answer.

1. Prefix Sums:
   • Build an array prefix where prefix[i] is the sum of nums[0] through nums[i-1].
   • This allows us to compute any subarray sum in O(1) time as prefix[right + 1] - prefix[left].
2. Find Boundaries with Monotonic Stack:
   • For each index i, find the furthest left index l and right index r such that nums[i] is the smallest in nums[l..r].
   • Use a stack to keep track of increasing elements to find the "previous less" (left) and "next less" (right) for each position efficiently.
3. Calculate Min-Product for Each Position:
   • For each position, calculate the min-product as nums[i] * (prefix[right[i] + 1] - prefix[left[i]]).
   • Track the maximum over all positions.
4. Return Result Modulo 10⁹+7:
   • Since the result can be large, return it modulo 10^9 + 7.

Example Walkthrough

Let's walk through an example with nums = [1, 2, 3, 2].

1. Prefix Sums:
   • prefix = [0, 1, 3, 6, 8]
2. Find Boundaries:
   • For nums[0]=1: left=0, right=3 (since 1 is the minimum in the whole array)
   • For nums[1]=2: left=1, right=3 (since 2 is the minimum in [1,2,3,2] at [1,3])
   • For nums[2]=3: left=2, right=2 (since 3 is the minimum only at itself)
   • For nums[3]=2: left=3, right=3 (since 2 is the minimum at itself)
3. Calculate Min-Product for Each:
   • For nums[0]=1: sum = prefix[4] - prefix[0] = 8, min-product = 1*8 = 8
   • For nums[1]=2: sum = prefix[4] - prefix[1] = 7, min-product = 2*7 = 14
   • For nums[2]=3: sum = prefix[3] - prefix[2] = 3, min-product = 3*3 = 9
   • For nums[3]=2: sum = prefix[4] - prefix[3] = 2, min-product = 2*2 = 4
4. Result: The maximum min-product is 14.

Time and Space Complexity

• Brute-force approach:
  • Time complexity: O(n^2) (since there are O(n^2) subarrays and each min and sum can take up to O(n) time)
  • Space complexity: O(1) (if not storing subarrays)
  • This is not feasible for large n.
• Optimized approach:
  • Time complexity: O(n) (each element is pushed and popped from the stack at most once, and prefix sums are built in O(n))
  • Space complexity: O(n) (for prefix sums, left/right boundaries, and stack)

Summary

The Maximum Subarray Min-Product problem illustrates how to optimize a seemingly brute-force problem using monotonic stacks and prefix sums. By focusing on each element as the potential minimum and efficiently determining its valid subarray range, we reduce the problem to linear time. The combination of stack-based boundary finding and prefix sum range queries is a powerful technique for many array problems, making this solution both efficient and elegant.