#1856

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Maximum Subarray Min-Product

The problem asks to find the maximum min-product of any non-empty subarray of nums.

Problem Statement

Given an array of integers nums, return the maximum min-product of any non-empty subarray. The min-product is defined as the product of the minimum value of the subarray and the sum of its elements. Since the result could be large, return it modulo 10^9 + 7. The subarrays are defined as contiguous elements from the original array.

You must maximize the min-product of the subarray before applying the modulo operation. The problem guarantees that the maximum min-product without modulo will fit within a 64-bit signed integer. Be mindful of constraints, where nums.length can be up to 10^5, and elements can be as large as 10^7.

Examples

Example 1

Input: nums = [1,2,3,2]

Output: 14

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

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

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

Solution Approach

Monotonic Stack for Subarray Management

Use a monotonic stack to help efficiently track the minimum element and manage the state of potential subarrays. The stack should maintain elements in increasing order, allowing quick access to the smallest value in any subarray.

Prefix Sum for Subarray Sum Calculation

Compute a prefix sum array to allow quick calculation of the sum of any subarray. By storing the cumulative sums up to each index, you can easily calculate the sum of subarrays as you traverse the array.

Modulo Operation After Maximization

Ensure the max min-product is computed before applying the modulo operation. This step is crucial, as applying the modulo too early will result in suboptimal solutions. The result should be modulo 10^9 + 7 as per the problem's requirements.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the chosen approach. Using a monotonic stack allows for a linear scan of the array with O(n) time complexity. The space complexity is O(n) due to the storage of the stack and prefix sum array.

What Interviewers Usually Probe

Assess if the candidate can optimize subarray operations using stacks.
Look for the candidate's ability to balance time complexity with large input sizes.
Test understanding of maximizing values before applying modulo operations.

Common Pitfalls or Variants

Common pitfalls

Forgetting to calculate the subarray sum efficiently using prefix sums.
Applying modulo too early, which can lead to suboptimal results.
Failing to correctly manage the stack to ensure minimum values are properly tracked.

Follow-up variants

Consider variations where negative numbers are allowed in the array.
What if you had to compute the result for multiple subarrays at once?
What changes if the array size is fixed or if a specific range of subarrays needs to be considered?

FAQ

What is the maximum subarray min-product problem?

The problem asks you to find the maximum min-product of any non-empty subarray, where the min-product is the product of the subarray's minimum value and its sum.

How can I solve the Maximum Subarray Min-Product problem efficiently?

Use a monotonic stack to manage the state of subarrays and a prefix sum array to calculate subarray sums efficiently. Maximize the min-product before applying modulo.

What are the main challenges of the Maximum Subarray Min-Product problem?

Key challenges include managing the monotonic stack correctly and ensuring the correct order of operations for the modulo operation after maximizing the min-product.

What is the time complexity of the best approach for this problem?

The optimal time complexity for solving this problem using a monotonic stack is O(n), where n is the length of the array.

How does GhostInterview help with the Maximum Subarray Min-Product problem?

GhostInterview provides guidance on using the right data structures, such as monotonic stacks and prefix sums, to solve the problem efficiently while avoiding common pitfalls.

terminal

Solution

Solution 1: Monotonic Stack + Prefix Sum

We can enumerate each element $nums[i]$ as the minimum value of the subarray, and find the left and right boundaries $left[i]$ and $right[i]$ of the subarray. Where $left[i]$ represents the first position strictly less than $nums[i]$ on the left side of $i$, and $right[i]$ represents the first position less than or equal to $nums[i]$ on the right side of $i$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        left = [-1] * n
        right = [n] * n
        stk = []
        for i, x in enumerate(nums):
            while stk and nums[stk[-1]] >= x:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and nums[stk[-1]] > nums[i]:
                stk.pop()
            if stk:
                right[i] = stk[-1]
            stk.append(i)
        s = list(accumulate(nums, initial=0))
        mod = 10**9 + 7
        return max((s[right[i]] - s[left[i] + 1]) * x for i, x in enumerate(nums)) % mod

Continue Practicing

#2281 sum of total strength of wizards #1124 longest well performing interval #1793 maximum score of a good subarray