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
- For each element treated as the subarray minimum, the best subarray is the widest one in which it remains the minimum.
- Those boundaries are the previous smaller and next smaller elements, found with a monotonic increasing stack.
- Prefix sums give the subarray sum in O(1), so the candidate is
nums[i] * (prefix[right] - prefix[left]). - 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 == nsentinel: 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.