1856. Maximum Subarray Min Product - cocoder39/coco39_LC GitHub Wiki

1856. Maximum Subarray Min-Product

prefix sum + Monotonically Increasing Stack

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        stack = []
        res = 0
        nums.append(0)
        prefixSum = [0]
        for i, num in enumerate(nums):
            prefixSum.append(prefixSum[-1] + num)
            while stack and num <= stack[-1][0]:
                val, _ = stack.pop()
                left = (stack[-1][1] + 1) if stack else 0
                arrSum = prefixSum[i] - prefixSum[left]
                res = max(res, val * arrSum)
            stack.append((num, i))
        
        while stack:
            val, right = stack.pop()
            left = (stack[-1][1] + 1) if stack else 0
            arrSum = prefixSum[right+1] - prefixSum[left]
            res = max(res, val * arrSum)
        return res % (10**9 + 7)