max-sub-min-prod

#define ll long long
class Solution {
public:
    int maxSumMinProduct(vector<int>& a) {
        const int mod = 1e9+7;
        int n = a.size();
        vector<ll>l(n),r(n);
        vector<ll>pref(n);
        ll cur=0;
        for(int i=0;i<n;i++){
            cur+=a[i];
            pref[i]=cur;
        }

        stack<int>s;
        for(int i=0;i<n;i++){
            while(!s.empty() and a[s.top()]>=a[i]) s.pop();
            if(s.empty()) l[i]=-1;
            else l[i]=s.top();
            s.push(i);
        }
        while(!s.empty()) s.pop();
         for(int i=n-1;i>=0;i--){
            while(!s.empty() and a[s.top()]>=a[i]) s.pop();
            if(s.empty()) r[i]=n;
            else r[i]=s.top();
             s.push(i);
        }
        ll mx = *max_element(a.begin(),a.end());
        ll ans = ((mx%mod)*(mx%mod))%mod;
        cur=ans;
        for(int i=0;i<n;++i) {
            int l_range = l[i],r_range = r[i];
cur =  ((1LL*(pref[r_range-1]-(l_range==-1?0:pref[l_range])%mod)*a[i])%mod);
        ans=max(ans,cur);

    }
        return ans;


    }
};