Description

Submission

class Solution {
    const int M = 1e9 + 7;
public:
    int maxSumMinProduct(vector<int>& nums) {
        nums.insert(nums.begin(), 0);
        int n = nums.size();

        // [1, n)
        vector<int> left(n);    // 1-index
        vector<int> right(n);
        vector<long long> presum(n);

        presum[0] = 0;
        for(int i = 1; i < n; ++i) {
            presum[i] = presum[i-1] + nums[i];
        }

        stack<int> stk;
        for(int i = 1; i < n; ++i) {
            while(!stk.empty() && nums[stk.top()] >= nums[i]) stk.pop();
            left[i] = stk.empty() ? 1 : stk.top() + 1;
            stk.push(i);
        }


        while(!stk.empty()) stk.pop();
        for(int i = n - 1; i >= 1; --i) {
            while(!stk.empty() && nums[stk.top()] > nums[i]) stk.pop();
            right[i] = stk.empty() ? n - 1 : stk.top() - 1;
            stk.push(i);
        }

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

        return ret % M;
    }
};

// traverse the whole array, assume that the current one is the smallest one in the subarray that it spans in both directions
// for each element x:
//     find the next smaller element in both side

//     3,1,5,6,4,2

//     increasing monostack
// 1 5 6 -> 1 -> 1 4

// 0 1 2 3 2