動機

把84的monotonic stack介紹借過來一下

1 2 3 .left. 7 .right. 2

right的數字大小一定是大於7!! left的數字一定是等於7

所以在這個區間中7一定是最小

這樣就可以用在題

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.

Given an array of integers nums, return the maximum min-product of any non-empty subarray of nums. Since the answer may be large, return it modulo 109 + 7.

Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [1,2,3,2]Output: 14Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2).2 * (2+3+2) = 2 * 7 = 14.

Example 2:

Input: nums = [2,3,3,1,2]Output: 18Explanation: The maximum min-product is achieved with the subarray [3,3] (minimum value is 3).3 * (3+3) = 3 * 6 = 18.

Example 3:

Input: nums = [3,1,5,6,4,2]Output: 60Explanation: The maximum min-product is achieved with the subarray [5,6,4] (minimum value is 4).4 * (5+6+4) = 4 * 15 = 60.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 107

Sol

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        sums = list(accumulate(nums, initial=0))
        nums += 0, # to compute last part autoly
        stk = []
        ret = 0
        for i,n in enumerate(nums):
            while stk and nums[stk[-1]] >= n:
                j = stk.pop()
                if stk:
                    ret = max(ret, nums[j]*(sums[i]-sums[stk[-1]+1]))
                else:
                    ret = max(ret, nums[j]*sums[i])
            stk += i,
        return ret % (10**9 + 7)