Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

const int N = 100000, INF = 1e9 + 7;
int a[N], lis[N], lds[N], n;

void calcLIS(int a[], int n, int res[]) {
    vector<int> last (n, INF);
    for(int i = 0; i < n; ++i) {
        res[i] = lower_bound(last.begin(), last.end(), a[i]) - last.begin();
        last[res[i]] = min(last[res[i]], a[i]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    reverse(a, a + n);
    calcLIS(a, n, lis);
    transform(a, a + n, a, negate<int>());
    calcLIS(a, n, lds);
    int res = 0;
    for(int i = 0; i < n; ++i)
        res = max(res, lis[i] + lds[i] + 1);
    cout << res << endl;
    return 0;
}

Code mẫu của skyvn97

#include<cstdio>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
int a[MAX];
int ci[MAX];
int cd[MAX];
int fi[MAX];
int fd[MAX];
int n;
void maximize(int &x,const int &y) {
    if (x<y) x=y;
}
void init(void) {
    scanf("%d",&n);
    FORD(i,n,1) scanf("%d",&a[i]);
}
void LIS(void) {
    int sz=1;
    fi[1]=1;
    ci[1]=1;    
    FOR(i,2,n) {
        if (a[i]<=a[ci[1]]) {
            fi[i]=1;
            ci[1]=i;
            continue;
        }
        if (a[i]>a[ci[sz]]) {
            sz++;
            fi[i]=sz;
            ci[sz]=i;
            continue;
        }
        int l=1;
        int r=sz;
        int m;
        while (true) {
            if (l==r) {
                m=r;
                break;
            }
            if (r-l==1) {
                if (a[i]>a[ci[r]]) m=r;
                else m=l;
                break;
            }
            m=(l+r)/2;
            if (a[i]>a[ci[m]]) l=m;
            else r=m-1;
        }
        fi[i]=m+1;
        if (a[ci[m+1]]>a[i]) ci[m+1]=i;
    }
}
void LDS(void) {
    int sz=1;
    fd[1]=1;
    cd[1]=1;
    FOR(i,2,n) {
        if (a[i]>=a[cd[1]]) {
            fd[i]=1;
            cd[1]=i;
            continue;
        }
        if (a[i]<a[cd[sz]]) {
            sz++;
            fd[i]=sz;
            cd[sz]=i;
            continue;
        }
        int l=1;
        int r=sz;
        int m;
        while (true) {
            if (l==r) {
                m=r;
                break;
            }
            if (r-l==1) {
                if (a[i]<a[cd[r]]) m=r;
                else m=l;
                break;
            }
            m=(l+r)/2;
            if (a[i]<a[cd[m]]) l=m;
            else r=m-1;         
        }
        fd[i]=m+1;
        if (a[cd[m+1]]<a[i]) cd[m+1]=i;
    }
}
void answer(void) {
    int res=0;  
    FOR(i,1,n) maximize(res,fi[i]+fd[i]-1);
    printf("%d",res);
}
int main(void) {
    //freopen("BEADS.INP","r",stdin);
    //freopen("BEADS.OUT","w",stdout);
    init();
    LIS();
    LDS();
    answer();
    return 0;
}