1856. Maximum Subarray Min-Product

#same like histogram solution
class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n=len(nums)
        pre=[0]
        for i in range(n):
            pre.append(pre[-1]+nums[i])
        q=deque()
        ans=0
        for i,j in enumerate(nums):
            newStart=i
            while q and q[-1][0]>j:
                item,popindex=q.pop()
                newStart=popindex
                total=pre[i]-pre[popindex]
                ans=max(ans,total*item)
            q.append((j,newStart))
        while q:
            item,popindex=q.pop()
            total=pre[-1]-pre[popindex]
            ans=max(ans,total*item)
        return ans