1856. Maximum Subarray Min-Product

1856. Maximum Subarray Min-Product (Medium)

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 109 + 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 = 14.

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).
3 * (3+3) = 3 * 6 = 18.

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 = 60.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 107

Companies:
Uber

Related Topics:
Binary Search, Dynamic Programming, Sort, Union Find, Queue, Dequeue

Solution 1. Next Smaller Element

Intuition: For a given number A[i], we only care about the subarray [p + 1, q - 1] where p and q are the index to the previous and next smaller element.

Why do we use the next/previous smaller element as the boundary?: For example:

 0 1 2 3 4 5 // index
[3,1,5,6,4,2] // value

For A[1] = 1, it's the smallest value of the entire array. So we should use the sum of the entire array.

For A[5] = 2, it's the second smallest value. We won't want to extend the subarray to index 1 because then the minimum value will become 1 and fall back to the previous case. So we only use subarray [5,6,4,2].

Similarly, for other numbers. In essense, we don't want to go over the previous/next smaller element.

Algorithm:

1. Store prefix sum in sum array.
2. Store the indexes to the previous/next smaller element into prev/next array.
3. For A[i], the max product including it is A[i] * SUM(prev[i] + 1, next[i] - 1) where SUM(i, j) is the sum of subarray A[i..j].

For "how to get the next smaller element", check out the mono-stack solutions to 496. Next Greater Element I (Easy)

// OJ: https://leetcode.com/problems/maximum-subarray-min-product/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int maxSumMinProduct(vector<int>& A) {
        long long mod = 1e9+7, N = A.size(), ans = 0;
        vector<long long> sum(N + 1); // prefix sum
        for (int i = 0; i < N; ++i) sum[i + 1] = sum[i] + A[i];
        vector<int> prev(N, -1), next(N, -1); // prev[i]/next[i] is the index to the previous/next smaller element
        vector<int> s; // a stack.
        for (int i = 0; i < N; ++i) { // compute the index to the previous smaller elements
            while (s.size() && A[s.back()] >= A[i]) s.pop_back();
            if (s.size()) prev[i] = s.back();
            s.push_back(i);
        }
        s.clear();
        for (int i = N - 1; i >= 0; --i) { // compute the index to the next smaller elements
            while (s.size() && A[s.back()] >= A[i]) s.pop_back();
            if (s.size()) next[i] = s.back();
            s.push_back(i);
        }
        for (int i = 0; i < N; ++i) {
            long long s = next[i] == -1 ? sum.back() : sum[next[i]];
            if (prev[i] != -1) {
                s -= sum[prev[i] + 1];
            }
            ans = max(ans, (long long) A[i] * s);
        }
        return ans % mod;
    }
};