LC-1856 Medium LeetCode

1856. Maximum Subarray Min-Product

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 39% Topics: Array, Stack, Monotonic Stack, Prefix Sum

Reading material

Arrays & Hashing 12 min Stacks & Queues 11 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def maxSumMinProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        MOD = 10**9+7
        prefix = [0]*(len(nums)+1)
        for i in xrange(len(nums)):
            prefix[i+1] = prefix[i]+nums[i]
        stk, result = [-1], 0
        for i in xrange(len(nums)+1):
            while stk[-1] != -1 and (i == len(nums) or nums[stk[-1]] >= nums[i]):
                result = max(result, nums[stk.pop()]*(prefix[(i-1)+1]-prefix[stk[-1]+1]))
            stk.append(i) 
        return result%MOD

Solution from kamyu104/LeetCode-Solutions · MIT