Advertisement
Kali_prasad

Maxsprod (qk22)

Apr 24th, 2022
46
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.73 KB | None | 0 0
  1. int Solution::maxSpecialProduct(vector<int> &A) {
  2.     int n=A.size();
  3.     vector<int> B(n,-1),C(n,-1);
  4.     stack<int> s;
  5.     for(int i=0;i<n;i++)
  6.     {
  7.         while(!s.empty()&&A[i]>=A[s.top()]){
  8.             s.pop();
  9.         }
  10.         if(!s.empty())
  11.         B[i]=s.top();
  12.         s.push(i);
  13.     }
  14.     s={};
  15.     for(int i=n-1;i>=0;i--)
  16.     {
  17.         while(!s.empty()&&A[i]>=A[s.top()]){
  18.             s.pop();
  19.         }
  20.         if(!s.empty())
  21.         C[i]=s.top();
  22.         s.push(i);
  23.     }
  24.     long long ans=0;
  25.     long long mod=(1e9+7);
  26.     for(int i=0;i<n;i++)
  27.     {
  28.         B[i]=max(B[i],0);
  29.         C[i]=max(C[i],0);
  30.         ans=max(ans,(B[i]*C[i]*1LL));
  31.        
  32.     }
  33.     ans%=mod;
  34.    
  35.     return ans;
  36. }
  37.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement