Maximum Subarray Min-Product — LeetCode 1856 Python Solution
MediumStackArrayPrefix SumMonotonic Stack
- Problem
- #1856
- Pattern
- Prefix Sum
- Reading time
- 4 min
- Source
- leetcode.com
The problem
The min-product of an array is equal to the minimum value in the array multiplied by the array's sum. For example, the array [3,2,5] (minimum value is 2) has a min-product of 2 * (3+2+5) = 2 * 10 = 20.
Example
- Input
- nums = [1,2,3,2]
- Output
- 14
- Explanation
- The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2).
Python solution
Python
class Solution:
def maxSumMinProduct(self, nums: List[int]) -> int:
n = len(nums)
left = [-1] * n
right = [n] * n
stk = []
for i, x in enumerate(nums):
while stk and nums[stk[-1]] >= x:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
while stk and nums[stk[-1]] > nums[i]:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
s = list(accumulate(nums, initial=0))
mod = 10**9 + 7
return max((s[right[i]] - s[left[i] + 1]) * x for i, x in enumerate(nums)) % modComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 1856. Maximum Subarray Min-Product is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1856. Maximum Subarray Min-Product?
- LeetCode 1856. Maximum Subarray Min-Product is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1856. Maximum Subarray Min-Product?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1856. Maximum Subarray Min-Product?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1856. Maximum Subarray Min-Product cover?
- LeetCode 1856. Maximum Subarray Min-Product is tagged Stack, Array, Prefix Sum and Monotonic Stack on LeetCode.