maximum-subarray-min-product.cpp

// Time:  O(n)
// Space: O(n)

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        static const int MOD = 1e9 + 7;

        vector<int64_t> prefix(nums.size() + 1);
        for (int i = 0; i < size(nums); ++i) {
           prefix[i + 1] = prefix[i] + nums[i];
        }
        vector<int> stk = {-1};
        int64_t result = 0;
        for (int i = 0; i <= size(nums); ++i) {
            while (stk.back() != -1 && (i == size(nums) || nums[stk.back()] >= nums[i])) {
                int j = stk.back();
                stk.pop_back();
                result = max(result, nums[j] * (prefix[(i - 1) + 1] - prefix[stk.back() + 1]));
            }
            stk.emplace_back(i);
        }
        return result % MOD;
    }
};