akashtadwai

max-sub-min-prod

Jul 24th, 2021
873
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define ll long long
  2. class Solution {
  3. public:
  4.     int maxSumMinProduct(vector<int>& a) {
  5.         const int mod = 1e9+7;
  6.         int n = a.size();
  7.         vector<ll>l(n),r(n);
  8.         vector<ll>pref(n);
  9.         ll cur=0;
  10.         for(int i=0;i<n;i++){
  11.             cur+=a[i];
  12.             pref[i]=cur;
  13.         }
  14.        
  15.         stack<int>s;
  16.         for(int i=0;i<n;i++){
  17.             while(!s.empty() and a[s.top()]>=a[i]) s.pop();
  18.             if(s.empty()) l[i]=-1;
  19.             else l[i]=s.top();
  20.             s.push(i);
  21.         }
  22.         while(!s.empty()) s.pop();
  23.          for(int i=n-1;i>=0;i--){
  24.             while(!s.empty() and a[s.top()]>=a[i]) s.pop();
  25.             if(s.empty()) r[i]=n;
  26.             else r[i]=s.top();
  27.              s.push(i);
  28.         }
  29.         ll mx = *max_element(a.begin(),a.end());
  30.         ll ans = ((mx%mod)*(mx%mod))%mod;
  31.         cur=ans;
  32.         for(int i=0;i<n;++i) {
  33.             int l_range = l[i],r_range = r[i];
  34. cur =  ((1LL*(pref[r_range-1]-(l_range==-1?0:pref[l_range])%mod)*a[i])%mod);
  35.         ans=max(ans,cur);
  36.        
  37.     }
  38.         return ans;
  39.  
  40.        
  41.     }
  42. };
RAW Paste Data