8 weeks ago

Sahil Kumar • 260

Gurugram

Apple Orchid Answer:-

We check for every element with the help of nextSmaller and prevSmaller element. 

int main() {
    stack <int> st;
     int n;
    cin>>n;
   vector <int > v(n);
    vector <int> nextSmaller(n,n);
    vector <int> prevSmaller(n,-1);
    for (int i=0;i<n;i++) {
    cin>>v[i];
    }
    
    for (int i=0;i<n;i++) {
        while (st.size() && v[st.top()]>v[i]) {
            
           nextSmaller[st.top()]=i;
            st.pop();
        }
        st.push(i);
    }
    
    for (int i=n-1;i>=0;i--) {
        
        while (st.size() && v[st.top()]>v[i]) {
            prevSmaller[st.top()]=i;
            st.pop();
        }
        st.push(i);
    }
     int ans=0;
    for (int i=0;i<n;i++) {
        ans=max(ans,(v[i]*(nextSmaller[i]-prevSmaller[i]-1)));
      
    }
    cout<<ans<<endl;
}