Description
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 is2) has a min-product of2 * (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: 14 Explanation: 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: 18 Explanation: 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: 60 Explanation: 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 <= 1051 <= nums[i] <= 107
Solution
Python3
class Solution:
def maxSumMinProduct(self, nums: List[int]) -> int:
M = 10 ** 9 + 7
n = len(nums)
res = 0
prefix = [0]
for x in nums:
prefix.append(x + prefix[-1])
l = [0] * n
r = [0] * n
stack = []
for i in range(n):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if stack:
l[i] = stack[-1] + 1
else:
l[i] = 0
stack.append(i)
stack = []
for i in reversed(range(n)):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if stack:
r[i] = stack[-1] - 1
else:
r[i] = n - 1
stack.append(i)
for i in range(n):
res = max(res, nums[i] * (prefix[r[i] + 1] - prefix[l[i]]))
return res % M