1856. Maximum Subarray Min-Product

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.

class Solution {
public:
    int maxSumMinProduct(vector<int>& n) {
        long res(0), sz(n.size()), mod(1e9 + 7);
        vector<long> sum(sz + 2), st;
        n.push_back(0);
        for (int i = 0; i <= sz; ++i) {
            sum[i + 1] = sum[i] + n[i];
            while (!st.empty() && (i == sz || n[st.back()] > n[i])) {
                int idx = st.back();
                st.pop_back();
                res = max(res, n[idx] * (sum[i] - sum[st.empty() ? 0 : st.back() + 1]));
            }
            st.push_back(i);
        }
        return res % mod;
    }
};