1856

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        // Find prefix sum.
        long long prefixSum[nums.size()+1];
        prefixSum[0] = nums[0];
        for(int i=1; i<nums.size(); i++){
            prefixSum[i] = prefixSum[i-1] + nums[i];
        }

        // Find left and right index for each element whose num value is less than element's value.
        vector<int> left(nums.size()), right(nums.size());
        left[0] = -1;
        for(int i=1; i<nums.size(); i++){
            int p = i-1;
            while(p >= 0 && nums[p] >= nums[i])
                p = left[p];
            left[i] = p;
        }
        int n = nums.size();
        right[n-1] = n;
        for(int i=n-1; i>=0; i--){
            int p = i+1;
            while(p < n && nums[p] >= nums[i])
                p = right[p];
            right[i] = p;
        }

        // For each index, compute answer from left and right index.
        long long ans =  0;
        for(int i=0; i<n; i++){
            long long int rsum = (right[i] == n) ? prefixSum[n-1] : prefixSum[max(0, right[i]-1)];
            long long int lsum = (left[i] == -1) ? 0 : prefixSum[left[i]];
            long long int sum  = rsum-lsum;
            ans = max(ans, nums[i]*sum);
        }
        return ans%(int(1e9+7));
    }
};