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 <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <cstdio>
using namespace std;

const int INF = (int) 1e9;
const int N = 50000;
int a[N];
int f[N];
int g[N];
int h[N];
int lis[N];
int bit[N];
int n;

int get(int x) {
    int result = -INF;
    while (x >= 0) {
        result = max(result, bit[x]);
        x -= ~x & (x + 1);
    }
    return result;
}

void update(int x, int v) {
    while (x < n) {
        bit[x] = max(bit[x], v);
        x |= x + 1;
    }
}

void calc(int f[]) {
    memset(bit, 0, sizeof bit);
    for (int i = 0; i < n; ++i) {
        lis[i] = max(1, get(a[i] - 1) + 1);
        update(a[i], lis[i]);
    }
    memset(bit, 0xc1, sizeof bit);
    for (int i = 0; i < n; ++i) {
        f[i] = get(n - 1 - (a[i] + 1)) + 1;
        update(n - 1 - a[i], max(lis[i] == 1 ? -INF : lis[i], f[i]));
    }
}

int main() {
#ifndef ONLINE_JUDGE
    assert(freopen("m.inp", "r", stdin));
    assert(freopen("m.out", "w", stdout));
#endif
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        h[i] = a[i];
    }
    sort(h, h + n);
    int m = unique(h, h + n) - h;
    for (int i = 0; i < n; ++i)
        a[i] = lower_bound(h, h + m, a[i]) - h;
    calc(f);
    reverse(a, a + n);
    calc(g);
    reverse(g, g + n);
    int answer = -1;
    for (int i = 0; i < n; ++i) {
        answer = max(answer, f[i] + g[i] - 1);
    }
    cout << answer << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 100005;
using namespace std;

struct bitUp {
    int bit[N];
    void upd(int i, int v) {
        for(i++; i < N; i += i & -i)
            bit[i] = max(bit[i], v);
    }
    int get(int i) {
        int s = 0;
        for(i++; i; i -= i & -i)
            s = max(s, bit[i]);
        return s;
    }
} bit1, bit3;

struct bitDown {
    int bit[N];
    void upd(int i, int v) {
        for(i++; i; i -= i & -i)
            bit[i] = max(bit[i], v);
    }
    int get(int i) {
        int s = 0;
        for(i++; i < N; i += i & -i)
            s = max(s, bit[i]);
        return s;
    }
} bit2, bit4;

II b[N];
int n;
int a[N], f[5][N];

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    FOR(i, 0, n) {
        cin >> a[i];
        b[i] = MP(a[i], i);
    }
    sort(b, b + n);
    int d = 0;
    FOR(i, 0, n) {
        if (i == 0 || b[i].X != b[i - 1].X) d++;
        a[b[i].Y] = d;
    }
    //FOR(i, 0, n) cout << a[i] << ' '; cout << endl;
    FOR(i, 0, n) {
        f[1][i] = bit1.get(a[i] - 1) + 1;
        bit1.upd(a[i], f[1][i]);
        //cout << f[1][i] << endl;
    }
    FOR(i, 0, n) {
        f[2][i] = bit2.get(a[i] + 1) + 1;
        if (f[2][i] > 2) bit2.upd(a[i], f[2][i]);
        if (f[1][i] >= 2) bit2.upd(a[i], f[1][i]);
        //cout << f[2][i] << endl;
    }
    FOR(i, 0, n) {
        f[3][i] = bit3.get(a[i] - 1) + 1;
        if (f[3][i] > 3) bit3.upd(a[i], f[3][i]);
        if (f[2][i] >= 3) bit3.upd(a[i], f[2][i]);
        //cout << f[3][i] << endl;
    }
    FOR(i, 0, n) {
        f[4][i] = bit4.get(a[i] + 1) + 1;
        if (f[4][i] > 4) bit4.upd(a[i], f[4][i]);
        if (f[3][i] >= 4) bit4.upd(a[i], f[3][i]);
        //cout << f[4][i] << endl;
    }
    int ans = 0;
    FOR(i, 0, n) ans = max(ans, f[4][i]);
    cout << ans;
    return 0;
}

Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<vector>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
void maximize(int &x,const int &y) {
    if (x<y) x=y;
}
class SegmentTree {
    private:
    int n;
    vector<int> tree;
    int getMax(int i,int l,int r,int u,int v) const {
        if (l>v || r<u || l>r || v<u) return (-MAX);
        if (u<=l && r<=v) return (tree[i]);
        int m=(l+r)>>1;
        int L=getMax(2*i,l,m,u,v);
        int R=getMax(2*i+1,m+1,r,u,v);
        return (max(L,R));
    }
    public:
    SegmentTree() {
        n=0;
    }
    SegmentTree(int n) {
        this->n=n;
        tree.assign(4*n+7,-MAX);
    }
    void update(int x,int v) {
        int i=1;
        int l=1;
        int r=n;
        while (true) {
            maximize(tree[i],v);
            if (l==r) return;
            int m=(l+r)>>1;
            if (x>m) {
                i=2*i+1;
                l=m+1;
            } else {
                i=2*i;
                r=m;
            }
        }
    }
    int getMax(int l,int r) const {
        return (getMax(1,1,n,l,r));
    }
};
int a[MAX],f[MAX][7],n;
vector<int> val;
void init(void) {
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&a[i]);
    FOR(i,1,n) val.push_back(a[i]);
    sort(val.begin(),val.end());
    val.resize(unique(val.begin(),val.end())-val.begin());
    FOR(i,1,n) a[i]=lower_bound(val.begin(),val.end(),a[i])-val.begin()+1;
}
void optimize(void) {
    REP(i,n) REP(j,5) f[i][j]=-MAX;
    SegmentTree tree[7];
    REP(i,5) tree[i]=SegmentTree(n);
    FOR(i,1,n) {
        f[i][0]=1;
        FOR(j,1,4) REP(k,2)
            maximize(f[i][j],j%2?tree[j-k].getMax(1,a[i]-1)+1:tree[j-k].getMax(a[i]+1,n)+1);
        REP(j,5) tree[j].update(a[i],f[i][j]);
    }
    int res=0;
    FOR(i,1,n) maximize(res,f[i][4]);
    printf("%d",res);
}
int main(void) {
    //freopen("M.INP","r",stdin);
    //freopen("M.OUT","w",stdout);
    init();
    optimize();
    return 0;
}