describe

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 10^9 + 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 = 14Copy the code

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).Copy the code

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 = 60Copy the code

Note:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^7
Copy the code

parsing

The smallest product of arrays is equal to the smallest value in the array multiplied by the sum of the arrays.

  • For example, the smallest product of the array [3,2,5] (minimum 2) is 2 * (3+2+5) = 2 * 10 = 20.

Given an integer array nums, returns the largest minimum product of any non-empty subarray of NUMs. Since the answer may be large, modulo it 10^9 + 7 and return. It is important to note that the minimum product should be maximized before performing modular operations.

The most violent solution is O(n^2), which loops through two layers to find all the subarrays, and then finds the minimum of each subarray multiplied by the sum, and finally finds the maximum, but this will definitely time out, because the condition says that the length of the array could be 10^5. Since each element is a positive integer greater than 0, we can find the left and right margins of the largest subarray whose minimum value is nums[I] for each element. This process can be solved by using the monadic stack idea, and then multiply the sum of the subarrays within the left and right margins by nums[I] using the prefix sum. Finally, after comparison to find the maximum value, take the modulus of (10**9+7) can return the answer.

answer

class Solution(object):
    def maxSumMinProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        N = len(nums)
        
        nextSmaller = [N] * N
        preSmaller = [-1] * N
        
        stack = []
        for i in range(N):
            while stack and nums[stack[-1]] > nums[i]:
                nextSmaller[stack.pop()] = i
            stack.append(i)
        
        stack = []
        for i in range(N-1,-1,-1):
            while stack and nums[stack[-1]] > nums[i]:
                preSmaller[stack.pop()] = i
            stack.append(i)
            
        presum = [0] * N
        presum[0] = nums[0]
        for i in range(1, N):
            presum[i] = presum[i-1] + nums[i]
            
        result = 0
        for i in range(N):
            a = 0 if preSmaller[i] == -1 else presum[preSmaller[i]]
            b = presum[nextSmaller[i]-1]
            result = max(result, (b-a) * nums[i])
            
        return result%(10**9+7)
            
        
        	      
		
Copy the code

The results

Given the linked list in the Python online submissions. Memory Usage: 10000 ms Submissions in Python online submissions for Maximum Subarray min-products.Copy the code

Original link: leetcode.com/problems/ma…

Your support is my biggest motivation