SMMR-157: Dunning-Kruger Effect

#include <bits/stdc++.h>

using namespace std;
const int N = 1e3;
int ar[N+10];
int L[N+10], dpL[N+10];
int R[N+10], dpR[N+10];
int n;

int bs(int l, int r, int val, char lr){
    int mn = r-l+1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(lr == 'l' and L[mid] <= val){
            mn = min(mn, mid);
            r = mid - 1;
        }
        else if(lr == 'r' and R[mid] <= val){
            mn = min(mn, mid);
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return mn;
}

int main(){

    scanf("%d", &n);

    for(int i=1;i<=n;i++) scanf("%d", &ar[i]);

    int l = 1;
    L[1] = ar[1];
    dpL[1] = 1;
    for(int i=2;i<=n;i++){
        if(L[l] > ar[i]){
            l ++;
            L[l] = ar[i];
        }
        else {
            L[bs(1, l, ar[i], 'l')] = ar[i];
        }
        dpL[i] = l;
    }

    int r = 1;
    R[1] = ar[n];
    dpR[n] = 1;
    for(int i=n-1;i>=1;i--){
        if(R[r] > ar[i]){
            r ++;
            R[r] = ar[i];
        }
        else {
            R[bs(1, r, ar[i], 'r')] = ar[i];
        }
        dpR[i] = r;
    }

    int mx = 1;
    for(int i=1;i<=n;i++) mx = max(mx, dpL[i] + dpR[i] - 1);

    printf("%d", mx);

    return 0;
}
/**
     for(int i=1;i<=n;i++) printf("%d ", dpL[i]);
     printf("\n");
     for(int i=1;i<=n;i++) printf("%d ", dpR[i]);
     printf("\n");
     for(int i=1;i<=l;i++) printf("%d ", L[i]);
     printf("\n");
     for(int i=1;i<=r;i++) printf("%d ", R[i]);
     printf("\n");
**/