We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Subarray Min-Product

Difficulty: Medium

Problem Description

Given an array of integers nums, return the maximum min-product of any non-empty subarray of nums. The min-product of an array is defined as the minimum value in the array multiplied by the array's sum. Since the answer may be large, return it modulo 10^9 + 7.

Key Insights

  • The min-product is maximized when the minimum value of the subarray is as large as possible.
  • To compute the sum of subarrays efficiently, a prefix sum approach can be utilized.
  • A monotonic stack can help in determining the range of subarrays for each element efficiently, allowing for the identification of the minimum value and its corresponding subarray sum.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution involves using a monotonic stack to find the range of subarrays for each element, which acts as the minimum within that subarray. For each element nums[i], we determine the left and right boundaries where it remains the minimum. Using these boundaries, we can compute the sum of the subarray defined by these boundaries. Finally, we calculate the min-product for each possible minimum and keep track of the maximum found.

Code Solutions

def maxSubarrayMinProduct(nums):
    MOD = 10**9 + 7
    n = len(nums)
    
    # Compute prefix sums
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + nums[i]
    
    # Monotonic stack to find the left and right boundaries
    left = [0] * n
    right = [0] * n
    stack = []
    
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    
    max_product = 0
    for i in range(n):
        min_val = nums[i]
        total_sum = prefix_sum[right[i]] - prefix_sum[left[i] + 1]
        max_product = max(max_product, min_val * total_sum)
    
    return max_product % MOD
← Back to All Questions