1856. Maximum Subarray Min Product (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def maxSumMinProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # monostack + prefix sum
        nums = [0] + nums + [0]
        ps = nums[:]
        for i in range(len(nums) - 1):
            ps[i + 1] += ps[i]
        result = 0
        monostack = []
        for i, num in enumerate(nums):
            while monostack and nums[monostack[-1]] > num:
                j = monostack.pop()
                result = max(result, (ps[i - 1] - ps[monostack[-1]]) * nums[j])
            monostack.append(i)
        return result % (10 ** 9 + 7)
        
        # heap + prefix sum TLE
        # calculate prefix sums
        nums = [0] + nums
        ps_nums = nums[:]
        n = len(nums)
        for i in range(n - 1):
            ps_nums[i + 1] += ps_nums[i]
        
        # save distinct nums to pq
        s = set(nums)
        heap = []
        for num in s:
            heapq.heappush(heap, num)
            
        result = 0
        visited = [0] * n
        h = {}
        while len(heap) > 1:
            num = heapq.heappop(heap)
            for i in range(n):
                if nums[i] == num:
                    visited[i] = 1
            j = -1
            flag = 0
            m = 0
            for i in range(n):
                if visited[i] == 0 and flag == 0:
                    j = i
                    flag = 1
                elif visited[i] == 1 and flag:
                    m = max(ps_nums[i - 1] - ps_nums[j - 1], m)
                    flag = 0
            if visited[-1] == 0:
                m = max(ps_nums[-1] - ps_nums[j - 1], m)
            result = m * heap[0]
        return result % (10 ** 9 + 7)