Maximum Subarray Min-Product

Medium
1405.

Maximum Subarray Min-Product

Maximum Subarray Min-Product is a medium coding problem on arrays, prefix sum and stack, asked in Amazon, Google and Uber interviews.

The min-product of an array is its minimum value multiplied by its sum; for example [3,2,5] has min-product 2 × (3 + 2 + 5) = 20.

Given an array nums of positive integers, find the largest min-product over all of its non-empty subarrays. Compare the exact products; only the final maximum is reduced, and you return it modulo 10^9 + 7.

(The value bound below is tighter than the original problem's so that the exact maximum stays below 2^53.)

Example 1

Input
nums = [3,1,4,4,2]
Output
32
Explanation
`[4,4]` gives 4 × 8 = 32.

Example 2

Input
nums = [2,5,4,1,3]
Output
36
Explanation
`[5,4]` gives 4 × 9 = 36.

Example 3

Input
nums = [100000,100000]
Output
999999867
Explanation
The whole array gives 100000 × 200000 = 2 · 10^10, which is 999999867 modulo 10^9 + 7.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumMinProduct = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Subarray Min-Product — Problem & Solution

Maximum Subarray Min-Product solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Subarray Min-Product is a medium coding problem on arrays, prefix sum and stack, asked in Amazon, Google and Uber interviews.

Problem statement

The min-product of an array is its minimum value multiplied by its sum; for example [3,2,5] has min-product 2 × (3 + 2 + 5) = 20.

Given an array nums of positive integers, find the largest min-product over all of its non-empty subarrays. Compare the exact products; only the final maximum is reduced, and you return it modulo 10^9 + 7.

(The value bound below is tighter than the original problem's so that the exact maximum stays below 2^53.)

Example 1

Input: nums = [3,1,4,4,2]
Output: 32
Explanation: `[4,4]` gives 4 × 8 = 32.

Example 2

Input: nums = [2,5,4,1,3]
Output: 36
Explanation: `[5,4]` gives 4 × 9 = 36.

Example 3

Input: nums = [100000,100000]
Output: 999999867
Explanation: The whole array gives 100000 × 200000 = 2 · 10^10, which is 999999867 modulo 10^9 + 7.

Constraints

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

Hints for Maximum Subarray Min-Product

  1. Hint 1

    Fix which element is the minimum. Since every value is positive, how far should the subarray extend around it?

  2. Hint 2

    Around index i, extend left and right as long as the values are at least nums[i] — a longer subarray with the same minimum has a larger sum.

  3. Hint 3

    Find those borders for every index with a monotonic stack (previous and next strictly smaller element) and read the sums from a prefix-sum array.

How to solve Maximum Subarray Min-Product

For each index treated as the minimum, the best subarray is the widest one in which it stays the minimum. A monotonic stack finds every such window in linear time and a prefix sum prices it.

Approach

  1. Build prefix sums P (as 64-bit integers — sums reach 10^10).
  2. With a monotonic stack find L[i], the previous index with a smaller value (or -1), and R[i], the next index with a smaller-or-equal value (or n).
  3. Candidate for i: nums[i] × (P[R[i]] - P[L[i] + 1]). Track the maximum.
  4. Return the maximum modulo 10^9 + 7.

Why it works

Take an optimal subarray and its minimum m. Because all values are positive, extending it over neighbours >= m keeps the minimum and grows the sum, so some optimal subarray is a maximal run of values >= m. The rightmost index holding m in that run has exactly that run as its window (strictly smaller to the left boundary, smaller-or-equal to the right one), so its candidate equals the optimum.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Take the maximum before the modulus — comparing reduced values picks the wrong subarray.
  • Sums overflow 32 bits; keep prefix sums and products in 64-bit.
  • Ties need no special care for a maximum: the rightmost copy of the minimum in a run sees the whole run, so stopping at equal values on the right loses nothing.

Reference solution

Python

from typing import List

def maxSumMinProduct(nums: List[int]) -> int:
    n = len(nums)
    prefix = [0] * (n + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    left = [-1] * n
    right = [n] * n
    st = []
    for i in range(n):
        while st and nums[st[-1]] >= nums[i]:
            right[st.pop()] = i
        left[i] = st[-1] if st else -1
        st.append(i)
    best = 0
    for i in range(n):
        best = max(best, nums[i] * (prefix[right[i]] - prefix[left[i] + 1]))
    return best % (10**9 + 7)

Java

public static int maxSumMinProduct(int[] nums) {
    int n = nums.length;
    long[] prefix = new long[n + 1];
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    int[] left = new int[n], right = new int[n], st = new int[n];
    int top = 0;
    for (int i = 0; i < n; i++) {
        right[i] = n;
        while (top > 0 && nums[st[top - 1]] >= nums[i]) right[st[--top]] = i;
        left[i] = top > 0 ? st[top - 1] : -1;
        st[top++] = i;
    }
    long best = 0;
    for (int i = 0; i < n; i++) {
        best = Math.max(best, nums[i] * (prefix[right[i]] - prefix[left[i] + 1]));
    }
    return (int) (best % 1000000007L);
}

C++

int maxSumMinProduct(vector<int>& nums) {
    int n = nums.size();
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    vector<int> left(n, -1), right(n, n), st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.back()] >= nums[i]) {
            right[st.back()] = i;
            st.pop_back();
        }
        left[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }
    long long best = 0;
    for (int i = 0; i < n; i++) {
        best = max(best, (long long)nums[i] * (prefix[right[i]] - prefix[left[i] + 1]));
    }
    return (int)(best % 1000000007LL);
}

JavaScript

var maxSumMinProduct = function(nums) {
    var n = nums.length;
    var prefix = new Array(n + 1).fill(0);
    for (var i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    var left = new Array(n), right = new Array(n).fill(n), st = [];
    for (var j = 0; j < n; j++) {
        while (st.length > 0 && nums[st[st.length - 1]] >= nums[j]) right[st.pop()] = j;
        left[j] = st.length > 0 ? st[st.length - 1] : -1;
        st.push(j);
    }
    var best = 0;
    for (var k = 0; k < n; k++) {
        var cand = nums[k] * (prefix[right[k]] - prefix[left[k] + 1]);
        if (cand > best) best = cand;
    }
    return best % 1000000007;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum