⚡Flashcard Drill➔
NeetCode #680LC-1856Medium1-D Dynamic Programming
← Back to All Problems

#680 · #1856 · Maximum Subarray Min-Product(子数组最小乘积的最大值)

📌 Problem Statement & Constraints

The min-product of a subarray is its minimum value multiplied by its sum. Given an array nums, return the maximum min-product over all subarrays, modulo 10^9 + 7. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^7.

💡 Core Algorithmic Approaches

  1. For each element treated as the subarray minimum, the best subarray is the widest one in which it remains the minimum.
  2. Those boundaries are the previous smaller and next smaller elements, found with a monotonic increasing stack.
  3. Prefix sums give the subarray sum in O(1), so the candidate is nums[i] * (prefix[right] - prefix[left]).
  4. Each index is pushed and popped once, giving O(n) overall.

💻 Benchmark Python3 Implementation

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        prefix = [0] * (n + 1)
        for i, x in enumerate(nums):
            prefix[i + 1] = prefix[i] + x
        res = 0
        stack = []                     # indices with increasing nums values
        for i in range(n + 1):
            while stack and (i == n or nums[stack[-1]] > nums[i]):
                j = stack.pop()
                left = stack[-1] + 1 if stack else 0
                total = prefix[i] - prefix[left]
                res = max(res, nums[j] * total)
            stack.append(i)
        return res % MOD

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each index is pushed and popped at most once.
💾 Space Complexity
O(n): the prefix array and the stack.

⚠️ Interview Pitfalls & Follow-ups

  • Reducing modulo before comparing: the maximum must be taken on the true values; only the final answer is reduced.
  • Misusing the comparison direction: popping while nums[stack[-1]] > nums[i] lets equal values extend the window, which is fine for a maximum.
  • Forgetting the i == n sentinel: without it the remaining stack is never flushed.
  • Computing the subarray sum with nested loops: that is O(n^2) and times out at 10^5 elements.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems