Maximum Subarray Min-Product

How it works

This variation uses an index-only stack and processes all elements in a single pass by treating the position after the array as a sentinel. When we pop an element, the current position is its right boundary, and the new stack top (or -1) is its left boundary. This eliminates the need to store value pairs in the stack.

Steps

1. Build a prefix sum array.
2. Iterate from index 0 to n (inclusive, where n acts as sentinel):
   • While the stack is non-empty and current element is smaller (or we reached the sentinel):
     • Pop index j from the stack.
     • Left boundary is stack top + 1 (or 0 if empty).
     • Right boundary is current index - 1.
     • Calculate nums[j] * range_sum and update the result.
   • Push current index to stack.
3. Return the maximum modulo 10^9 + 7.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Integer Overflow Before Taking Modulo

The min-product can be extremely large (minimum value up to 10^7 times sum up to 10^14), exceeding 32-bit integer limits. You must use 64-bit integers for intermediate calculations and only apply modulo at the very end when returning the result. Applying modulo during comparisons breaks the max logic since you're comparing reduced values.

Confusing Min-Product with Other Formulas

The min-product is min(subarray) * sum(subarray), which combines both the minimum element and the subarray sum. This is different from problems involving just the minimum times length, or just the sum. Make sure to compute prefix sums for efficient range sum queries and track minimums correctly.

Off-by-One Errors with Prefix Sum Boundaries

When using prefix sums, the sum of elements from index l to r (inclusive) is prefix[r+1] - prefix[l], not prefix[r] - prefix[l]. Getting this boundary wrong by one index leads to incorrect subarray sums and wrong answers.

from typing import List

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]

        res, stack = 0, []
        for i in range(n + 1):
            while stack and (i == n or nums[i] < nums[stack[-1]]):
                j = stack.pop()
                start = 0 if not stack else stack[-1] + 1
                res = max(res, nums[j] * (prefix_sum[i] - prefix_sum[start]))
            stack.append(i)

        return res % (10 ** 9 + 7)

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        int n = nums.size();
        vector<long long> prefixSum(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        long long res = 0;
        const int mod = 1e9 + 7;
        stack<int> st;
        for (int i = 0; i <= n; i++) {
            while (!st.empty() && (i == n || nums[i] < nums[st.top()])) {
                int j = st.top();
                st.pop();
                int start = st.empty() ? 0 : st.top() + 1;
                res = max(res, (long long) nums[j] * (prefixSum[i] - prefixSum[start]));
            }
            st.push(i);
        }

        return res % mod;
    }
};