I Couldn't Optimize Max Sum Min-Product Until I Flipped the Question

This is part of a series where I break down coding concepts I understand when reading about them but struggle to reuse when I actually need them. Not tutorials. Personal learning journeys that break down the "why does this actually work" part.

The problem that tripped me up

LeetCode 1856: Maximum Subarray Min-Product. The formula is straightforward. For any subarray, multiply the minimum element by the sum of the subarray. Find the maximum across all possible subarrays.

I could see the O(n^2) solution clearly. Try every subarray, track the running min and running sum, update the max. But dropping to O(n)? That's where I got stuck.

Where my intuition went wrong

My first instinct was a sliding window approach. Add an element to the range, check if it improves the answer, otherwise store the max and reset. It felt right because you're building ranges and checking them.

But here's why it fails: the decision to "keep going or reset" depends on both the sum AND the minimum changing at the same time. Adding a large number helps the sum but might not help if the min stays low. Adding a small number hurts the min but you don't know yet whether the sum makes up for it. There's no clean greedy condition to check.

I was stuck because I was asking the wrong question.

The reframe that made it click

Instead of asking "what's the best range?", flip it:

For each element, what's the widest subarray where THAT element is the minimum?

Why does this cover every possible answer? Because whatever the optimal subarray is, it has some minimum element. That minimum is one of the values in the array. So if you check every element as a potential minimum and find its best subarray, you're guaranteed to find the answer.

This changes the problem from "search all subarrays" to "for each element, find its boundaries." And finding boundaries is exactly what a monotonic stack does.

How the monotonic stack finds boundaries

You maintain a stack of indices where the values are strictly increasing from bottom to top. As you iterate through the array, when you encounter a value smaller than or equal to the stack top, you pop.

The magic: when an element gets popped, it has found both its boundaries in that single moment.

• Right boundary: the current element (the one causing the pop). It's smaller, so the popped element can't be the minimum past this point.
• Left boundary: whatever is now on top of the stack after popping. It's the nearest smaller element to the left.

The subarray where the popped element is the minimum goes from left_boundary + 1 to right_boundary - 1.

Let me trace through [3, 1, 6, 4, 5, 2]:

i=0, val=3: push 0          stack: [0]
i=1, val=1: pop 0, push 1   stack: [1]
  → popped 3: right=1, left=-1 (empty stack), subarray=[0..0]
i=2, val=6: push 2          stack: [1, 2]
i=3, val=4: pop 2, push 3   stack: [1, 3]
  → popped 6: right=3, left=1, subarray=[2..2]
i=4, val=5: push 4          stack: [1, 3, 4]
i=5, val=2: pop 4           stack: [1, 3]
  → popped 5: right=5, left=3, subarray=[4..4]
         pop 3              stack: [1]
  → popped 4: right=5, left=1, subarray=[2..4]

When the stack is empty after popping, the left boundary is -1 (meaning "nothing smaller exists to the left, extend all the way to index 0"). After processing all elements, anything still in the stack has no right boundary, so it extends all the way to the end of the array (right boundary = n).

Prefix sums for O(1) range sums

Once you have boundaries for each element, you need the sum of that subarray. Building a prefix sum array with a leading zero handles this cleanly:

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

# sum of nums[a..b] = prefix[b+1] - prefix[a]

The leading zero is important. Without it, getting the sum starting from index 0 requires special-case handling that leads to off-by-one bugs (I know because I made this exact mistake).

The full solution

def maxSumMinProduct(self, nums):
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)

    result = 0
    stack = []

    for i in range(len(nums)):
        while stack and nums[stack[-1]] >= nums[i]:
            popped = stack.pop()
            left = stack[-1] if stack else -1
            right = i
            total = prefix[right] - prefix[left + 1]
            result = max(result, nums[popped] * total)
        stack.append(i)

    # drain remaining elements
    while stack:
        popped = stack.pop()
        left = stack[-1] if stack else -1
        right = len(nums)
        total = prefix[right] - prefix[left + 1]
        result = max(result, nums[popped] * total)

    return result % (10**9 + 7)

Mistakes I actually made

Using > instead of >= in the while condition. With just >, equal elements don't get popped. This means when duplicates exist, a later equal element might compute an incorrect left boundary because its twin is still sitting in the stack.

Using the index as the value. I wrote result = max(result, popped * total) where popped is the index I popped from the stack. Should have been nums[popped]. The index is just a position. The value at that position is what you multiply by.

Prefix sum without the leading zero. My first attempt used pref_arr[0] = nums[0], which made the formula for getting sums starting from index 0 a special case. Adding the leading zero makes every range use the same formula: prefix[right] - prefix[left + 1].

What to practice next

These all use the same "for each element, find its boundaries" pattern with a monotonic stack:

1. Largest Rectangle in Histogram (LeetCode 84). The classic. For each bar, find the widest rectangle where it's the shortest bar. Almost identical logic.
2. Sum of Subarray Minimums (LeetCode 907). Instead of max(min * sum), you're summing all the min-products. Same boundary finding, different aggregation.
3. Sum of Subarray Ranges (LeetCode 2104). Find both the min-contribution and max-contribution of each element using two monotonic stacks (one increasing, one decreasing).
4. Trapping Rain Water (LeetCode 42). Uses a monotonic decreasing stack. When you pop, the boundaries tell you the width and height of water you can trap.
5. Next Greater Element II (LeetCode 503). Simpler. Good warm-up for understanding the pop mechanics without the prefix sum layer.

I'd recommend doing them in order: 84 first (it's the closest to what we just solved), then 907, then the rest.

I'm building Levelop to help people get better at problems like these. If you want more breakdowns like this, check it out.