[Medium] 1856. Maximum Sum of Minimum Product

The minimum product of a subarray is the minimum value in the subarray multiplied by the sum of the subarray.

Given an array of integers nums, return the maximum minimum product of any non-empty subarray of nums.

Examples

Example 1:

Input: nums = [1,2,3,2]
Output: 14
Explanation: 
- Subarray [2,3,2] has minimum value 2 and sum 7
- Minimum product = 2 * 7 = 14
- This is the maximum minimum product

Example 2:

Input: nums = [2,3,3,1,2]
Output: 18
Explanation: 
- Subarray [3,3,1,2] has minimum value 1 and sum 9
- Minimum product = 1 * 9 = 9
- Subarray [2,3,3,1,2] has minimum value 1 and sum 11
- Minimum product = 1 * 11 = 11
- Subarray [3,3] has minimum value 3 and sum 6
- Minimum product = 3 * 6 = 18
- Maximum is 18

Example 3:

Input: nums = [3,1,5,6,4,2]
Output: 60
Explanation: 
- Subarray [5,6,4,2] has minimum value 2 and sum 17
- Minimum product = 2 * 17 = 34
- Subarray [5,6] has minimum value 5 and sum 11
- Minimum product = 5 * 11 = 55
- Subarray [5,6,4] has minimum value 4 and sum 15
- Minimum product = 4 * 15 = 60
- Maximum is 60

Constraints

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

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Subarray definition: Does a subarray need to be contiguous? (Assumption: Yes - subarray is contiguous by definition)
Minimum product calculation: How is minimum product calculated? (Assumption: For each subarray, find minimum value and sum, then multiply them - min(subarray) * sum(subarray))
Optimization goal: What are we optimizing for? (Assumption: Maximum value among all minimum products from all subarrays)
Return value: What should we return? (Assumption: Maximum minimum product - integer, modulo 10^9 + 7)
Empty subarray: Can an empty subarray be considered? (Assumption: No - subarray must be non-empty)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Initial Thought: “I need to find maximum sum × minimum. Let me check all possible subarrays.”

Naive Solution: Check all possible subarrays, for each compute sum and minimum, calculate product, track maximum.

Complexity: O(n³) time, O(1) space

Issues:

O(n³) time - very inefficient
Repeats computation for overlapping subarrays
Doesn’t leverage any optimization
Can be optimized significantly

Step 2: Semi-Optimized Approach (7 minutes)

Insight: “I can fix minimum value and find maximum sum subarray with that minimum.”

Improved Solution: For each element as minimum, find maximum sum subarray where this element is minimum. Use prefix sum to compute sums efficiently.

Complexity: O(n²) time, O(n) space

Improvements:

O(n²) time is better
Prefix sum enables O(1) sum queries
Still O(n²) for checking all subarrays
Can optimize further

Step 3: Optimized Solution (8 minutes)

Final Optimization: “I can use monotonic stack to find range where each element is minimum.”

Best Solution: Use monotonic stack to find left and right boundaries where each element is minimum. Use prefix sum for range sums. For each element, compute sum × minimum for its range.

Complexity: O(n) time, O(n) space

Key Realizations:

Monotonic stack finds minimum ranges efficiently
Prefix sum enables O(1) range sum queries
O(n) time is optimal - process each element once
O(n) space for stack and prefix sum is necessary

Solution: Monotonic Stack with Prefix Sum

Time Complexity: O(n) where n is the length of array
Space Complexity: O(n) for prefix array and stack

Use monotonic stack to find the range where each element is minimum, then calculate the maximum product using prefix sums.

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        int n = nums.size();
        vector<long long> prefix(n + 1, 0);
        
        // Build prefix sum array
        for(int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        vector<int> left(n, -1), right(n, n);
        stack<int> s;
        
        // Find boundaries in single pass
        for(int i = 0; i < n; i++) {
            // Find right boundaries for elements in stack
            while(!s.empty() && nums[s.top()] >= nums[i]) {
                right[s.top()] = i;
                s.pop();
            }
            // Set left boundary for current element
            if(!s.empty()) left[i] = s.top();
            s.push(i);
        }
        
        long long maxProduct = 0;
        
        // Calculate maximum product for each element as minimum
        for(int i = 0; i < n; i++) {
            long long totalSum = prefix[right[i]] - prefix[left[i] + 1];
            maxProduct = max(maxProduct, totalSum * nums[i]);
        }
        
        return (int)(maxProduct % 1000000007);
    }
};

How the Algorithm Works

Key Insight: For each element, find the largest subarray where it is the minimum, then calculate the product of minimum value and subarray sum.

Steps:

Build prefix sum array for efficient range sum calculation
Find boundaries in single pass using monotonic stack:
- When popping elements, set their right boundary to current index
- Set current element’s left boundary to stack top
For each element as minimum:
- Calculate subarray sum using prefix array
- Calculate product: sum * minimum_value
- Update maximum product
Return result modulo 10^9 + 7

Step-by-Step Example

Example: `nums = [1,2,3,2]`

Step 1: Build prefix sum array

nums = [1, 2, 3, 2]
prefix = [0, 1, 3, 6, 8]

Step 2: Find left boundaries (nearest smaller to the left)

nums = [1, 2, 3, 2]
left = [-1, 0, 1, 0]

Step 3: Find right boundaries (nearest smaller to the right)

nums = [1, 2, 3, 2]
right = [4, 3, 4, 4]

Step 4: Calculate products for each element as minimum

Index	Element	Left	Right	Subarray	Sum	Product
0	1	-1	4	[1,2,3,2]	8	1×8 = 8
1	2	0	3	[2,3]	5	2×5 = 10
2	3	1	4	[3]	3	3×3 = 9
3	2	0	4	[2,3,2]	7	2×7 = 14

Maximum product: 14

Algorithm Breakdown

Single Pass Boundary Finding:

for(int i = 0; i < n; i++) {
    // Find right boundaries for elements in stack
    while(!s.empty() && nums[s.top()] >= nums[i]) {
        right[s.top()] = i;
        s.pop();
    }
    // Set left boundary for current element
    if(!s.empty()) left[i] = s.top();
    s.push(i);
}

Process:

When popping elements: Set their right boundary to current index
Set left boundary: Current element’s left boundary is stack top
Push current index to stack
Single pass: Both boundaries found in one traversal

Product Calculation:

for(int i = 0; i < n; i++) {
    long long totalSum = prefix[right[i]] - prefix[left[i] + 1];
    maxProduct = max(maxProduct, totalSum * nums[i]);
}

Process:

Calculate subarray sum using prefix array
Multiply by minimum value (current element)
Update maximum product

Complexity Analysis

Operation	Time Complexity	Space Complexity
Prefix sum	O(n)	O(n)
Single pass boundaries	O(n)	O(n)
Product calculation	O(n)	O(1)
Total	O(n)	O(n)

Where n is the length of the array.

Edge Cases

Single element: nums = [5] → 5 * 5 = 25
All same elements: nums = [3,3,3] → 3 * 9 = 27
Increasing array: nums = [1,2,3,4] → 1 * 10 = 10
Decreasing array: nums = [4,3,2,1] → 1 * 10 = 10

Key Insights

Monotonic Stack:

Maintains order: Elements in decreasing order
Efficient removal: Can remove multiple elements at once
Boundary finding: Finds nearest smaller elements efficiently
O(n) complexity: Each element pushed and popped once

Prefix Sum:

Range sum calculation: O(1) for any subarray sum
Efficient computation: Pre-computed sums
Memory trade-off: Uses O(n) extra space for O(1) queries

Product Maximization:

Minimum as pivot: Consider each element as minimum
Largest subarray: Find maximum subarray where element is minimum
Greedy approach: Take largest possible subarray for each minimum

Detailed Example Walkthrough

Example: `nums = [2,3,3,1,2]`

Step 1: Prefix sum array

nums = [2, 3, 3, 1, 2]
prefix = [0, 2, 5, 8, 9, 11]

Step 2: Left boundaries

nums = [2, 3, 3, 1, 2]
left = [-1, 0, 0, -1, 3]

Step 3: Right boundaries

nums = [2, 3, 3, 1, 2]
right = [3, 3, 3, 5, 5]

Step 4: Product calculation

Index	Element	Left	Right	Subarray	Sum	Product
0	2	-1	3	[2,3,3]	8	2×8 = 16
1	3	0	3	[3]	3	3×3 = 9
2	3	0	3	[3]	3	3×3 = 9
3	1	-1	5	[2,3,3,1,2]	11	1×11 = 11
4	2	3	5	[2]	2	2×2 = 4

Maximum product: 16

Alternative Approaches

Approach 1: Brute Force

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        long long maxProduct = 0;
        int n = nums.size();
        
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                int minVal = *min_element(nums.begin() + i, nums.begin() + j + 1);
                long long sum = accumulate(nums.begin() + i, nums.begin() + j + 1, 0LL);
                maxProduct = max(maxProduct, minVal * sum);
            }
        }
        
        return (int)(maxProduct % 1000000007);
    }
};

Time Complexity: O(n^3)
Space Complexity: O(1)

Approach 2: Divide and Conquer

class Solution {
private:
    long long maxProduct(vector<int>& nums, int left, int right) {
        if(left > right) return 0;
        if(left == right) return (long long)nums[left] * nums[left];
        
        int minIdx = min_element(nums.begin() + left, nums.begin() + right + 1) - nums.begin();
        long long sum = accumulate(nums.begin() + left, nums.begin() + right + 1, 0LL);
        long long product = (long long)nums[minIdx] * sum;
        
        return max({product, maxProduct(nums, left, minIdx - 1), maxProduct(nums, minIdx + 1, right)});
    }
    
public:
    int maxSumMinProduct(vector<int>& nums) {
        return (int)(maxProduct(nums, 0, nums.size() - 1) % 1000000007);
    }
};

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

Common Mistakes

Wrong boundary calculation: Not handling empty stack correctly
Index off-by-one: Incorrect prefix sum calculation
Overflow issues: Not using long long for large products
Modulo placement: Applying modulo at wrong time

Why This Solution Works

Monotonic Stack:

Efficient boundary finding: O(n) time to find all boundaries
Maintains order: Elements in decreasing order
Optimal removal: Can remove multiple elements at once
Correct boundaries: Finds nearest smaller elements accurately

Prefix Sum:

Range sum calculation: O(1) for any subarray sum
Efficient computation: Pre-computed sums
Memory trade-off: Uses O(n) extra space for O(1) queries

Product Maximization:

Minimum as pivot: Consider each element as minimum
Largest subarray: Find maximum subarray where element is minimum
Greedy approach: Take largest possible subarray for each minimum
Optimal result: Ensures maximum product calculation

Robina Li

[Medium] 1856. Maximum Sum of Minimum Product

[Medium] 1856. Maximum Sum of Minimum Product

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Solution: Monotonic Stack with Prefix Sum

How the Algorithm Works

Step-by-Step Example

Example: `nums = [1,2,3,2]`

Algorithm Breakdown

Single Pass Boundary Finding:

Product Calculation:

Complexity Analysis

Edge Cases

Key Insights

Monotonic Stack:

Prefix Sum:

Product Maximization:

Detailed Example Walkthrough

Example: `nums = [2,3,3,1,2]`

Alternative Approaches

Approach 1: Brute Force

Approach 2: Divide and Conquer

Common Mistakes

Why This Solution Works

Monotonic Stack:

Prefix Sum:

Product Maximization:

Related Posts

Recent Posts

[Medium] 1856. Maximum Sum of Minimum Product

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Solution: Monotonic Stack with Prefix Sum

How the Algorithm Works

Step-by-Step Example

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

Algorithm Breakdown

Single Pass Boundary Finding:

Product Calculation:

Complexity Analysis

Edge Cases

Key Insights

Monotonic Stack:

Prefix Sum:

Product Maximization:

Detailed Example Walkthrough

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

Alternative Approaches

Approach 1: Brute Force

Approach 2: Divide and Conquer

Common Mistakes

Related Problems

Why This Solution Works

Monotonic Stack:

Prefix Sum:

Product Maximization:

Related Posts

Recent Posts

Example: `nums = [1,2,3,2]`

Example: `nums = [2,3,3,1,2]`