Mountain Range

Implementation

C++

                                    #include "bits/stdc++.h"
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);

const int N = 200005;
int segtree[4*N];

int merge(int l, int r) {
    return max(l,r);
}

void update(int node,int l, int r, int pos, int val) {
    if(l>r or l>pos or r<pos) return;
    if( l == r ) {
        segtree[node] = val;
        return;
    }
    int m = (l+r)/2;
    update(node*2,l,m,pos,val);
    update(node*2+1,m+1,r,pos,val);
    segtree[node] = merge(segtree[node*2],segtree[node*2+1]);
}

int query(int node, int l, int r, int L, int R) {
    if(l>r or l>R or r<L) return 0;
    if( l >= L and r <= R ) {
        return segtree[node];
    }
    int m = (l+r)/2;
    return merge( query(node*2,l,m,L,R),query(node*2+1,m+1,r,L,R));
}

void solve() {

    int n;
    cin >> n;
    int ara[n];
    pair<int,int> para[n+1];

    for(int i=1;i<=n;i++) { 
        cin >> ara[i];
        para[i] = {ara[i],i};
    }
    sort(para+1,para+n+1);
    ara[0] = 1000000008; ara[n+1] = 1000000008;
    vector<int> lft(n+2,0);
    vector<int> rht(n+2,0);
    vector<int> st;
    st.push_back(0);
    for(int i=1;i<=n;i++) {
        while(ara[st.back()] < ara[i]) st.pop_back();
        lft[i] = st.back();
        st.push_back(i);
    }
    st.clear();

    st.push_back(n+1);
    for(int i=n;i>0;i--) {
        while(ara[st.back()] < ara[i]) st.pop_back();
        rht[i] = st.back();
        st.push_back(i);
    }

    int mx = 0;
    for(int i=1;i<=n;i++) {
        int ind = para[i].second;
        int rs = query(1,1,n,lft[ind]+1,rht[ind]-1)+1;
        mx = max(mx,rs);
        update(1,1,n,ind,rs);
    }
    cout<<mx<<endl;
}

int main() {
    FASTIO;
    solve();
}