Maximum Subarray Min-Product

medium array monotonic stack prefix sum

Problem

The min-product of a contiguous subarray is its minimum element multiplied by the sum of all its elements. Given an array of positive integers nums, return the largest min-product over every possible subarray, taken modulo 10^9 + 7. The maximum itself is found before applying the modulo.

Inputnums = [1, 2, 3, 2]

Output14

The subarray [2, 3, 2] has minimum 2 and sum 7, so its min-product is 2 × 7 = 14, the best of any subarray.

nums (comma-separated, positive)

def maxSumMinProduct(nums):
    MOD = 10**9 + 7
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = 0
    st = []
    for i in range(n + 1):
        cur = nums[i] if i < n else 0
        while st and nums[st[-1]] >= cur:
            j = st.pop()
            left = st[-1] + 1 if st else 0
            total = prefix[i] - prefix[left]
            best = max(best, nums[j] * total)
        st.append(i)
    return best % MOD

function maxSumMinProduct(nums) {
  const MOD = 1000000007n;
  const n = nums.length;
  const prefix = new Array(n + 1).fill(0n);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + BigInt(nums[i]);
  let best = 0n;
  const st = [];
  for (let i = 0; i <= n; i++) {
    const cur = i < n ? nums[i] : 0;
    while (st.length && nums[st[st.length - 1]] >= cur) {
      const j = st.pop();
      const left = st.length ? st[st.length - 1] + 1 : 0;
      const total = prefix[i] - prefix[left];
      const prod = BigInt(nums[j]) * total;
      if (prod > best) best = prod;
    }
    st.push(i);
  }
  return Number(best % MOD);
}

class Solution {
    public int maxSumMinProduct(int[] nums) {
        final long MOD = 1000000007L;
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        long best = 0;
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i <= n; i++) {
            int cur = i < n ? nums[i] : 0;
            while (!st.isEmpty() && nums[st.peek()] >= cur) {
                int j = st.pop();
                int left = st.isEmpty() ? 0 : st.peek() + 1;
                long total = prefix[i] - prefix[left];
                best = Math.max(best, (long) nums[j] * total);
            }
            st.push(i);
        }
        return (int) (best % MOD);
    }
}

int maxSumMinProduct(vector<int>& nums) {
    const long long MOD = 1000000007LL;
    int n = (int) nums.size();
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    long long best = 0;
    stack<int> st;
    for (int i = 0; i <= n; i++) {
        int cur = i < n ? nums[i] : 0;
        while (!st.empty() && nums[st.top()] >= cur) {
            int j = st.top(); st.pop();
            int left = st.empty() ? 0 : st.top() + 1;
            long long total = prefix[i] - prefix[left];
            best = max(best, (long long) nums[j] * total);
        }
        st.push(i);
    }
    return (int) (best % MOD);
}

Explanation

Trying every subarray and computing its minimum and sum would be far too slow. The key insight is to flip the question: instead of asking "what is the min of this subarray?", we ask for each element nums[j], "what is the widest subarray in which nums[j] is the minimum?". Because all values are positive, a wider span always has a larger (or equal) sum, so the best min-product for a given element comes from its maximal span.

That maximal span stretches left and right until we hit an element strictly smaller than nums[j]. A monotonic stack of indices, kept in non-decreasing value order, finds those boundaries in one pass: when the incoming element is smaller than the value on top of the stack, that top element can no longer extend rightward, so we pop it and finalize its span right there.

When we pop index j, its right boundary is the current position i and its left boundary is just after the new stack top (or the array start if the stack is empty). The sum over that span is computed instantly with a prefix-sum array: prefix[i] − prefix[left]. We multiply by nums[j] and keep the running maximum.

A sentinel value of 0 at index n guarantees every remaining element gets popped and finalized by the end. Only at the very end do we apply mod 10^9 + 7 — the comparison to find the maximum must use the true product.

Example: nums = [1, 2, 3, 2]. When 3 is popped its span is just [3] (product 9). When the 2 values get finalized, their span covers [2, 3, 2] with sum 7, giving 2 × 7 = 14. The element 1 spans the whole array, sum 8, product 8. The largest is 14.

Each index is pushed and popped exactly once, so the whole thing runs in linear time.

Time: O(n) Space: O(n)