HỌC TIN CÙNG THỦ KHOA

Mời các bạn download tại: Click here

Tài liệu tham khảo: https://www.giaithuatlaptrinh.com/?p=78

#include <bits/stdc++.h>

using namespace std;

const int oo = INT_MAX/2;
const int MAXN = 30005;
int Truoc[MAXN];
int n;
int a[MAXN], b[MAXN], F[MAXN];

void TruyVet(int i) {
    if (Truoc[i] == -1) cout << a[i];
        else {
            TruyVet(Truoc[i]);
            cout << " " << a[i];
        }
}

bool cmp(int cda, int cdk) {
    return a[cda] < a[cdk];
}

int main() {
    ///freopen("toson.inp", "r", stdin);

    /*
    .INP
    8
    3 2 2 6 5 4 7 1

    .OUT
    3
    2 4 7
    */

    cin >> n;
    cout << "   ";
    for (int i = 1; i <= n; i++) {
        printf("%-10d ", i);
    }
    cout << endl;
    cout << "   ";
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        printf("%-10d ", a[i]);
    }
    cout << endl;

    for (int i = 1; i <= n; i++)
        b[i] = +oo;

    int ans = 0;

    b[0] = -1;
    int k;

    for (int i = 1; i <= n; i++) {
        int vt = lower_bound(b+1, b+ans+1, i, cmp) - b;
        ///int vt = upper_bound(b+1, b+ans+1, i, cmp) - b;
        F[i] = vt; /// Dung de truy vet theo Cach 1
        b[vt] = i;

        if (ans < vt) {
            ans = vt;
            k = i;
        }

        Truoc[i] = b[vt - 1]; /// Dung de truy vet theo Cach 2

        cout << F[i] << ": ";

        for (int j = 1; j <= n; j++)
            if (b[j] != +oo)
                printf("%-10d ", a[b[j]]);
            else printf("%-10s ", "+oo");
        cout << endl;

    }
    cout << "Do dai day con don dieu tang dai nhat: " << ans << endl;

    cout << "- Cach 1: " << endl;
    int m = ans;
    int ma = +oo;
    vector<int> T;
    for (int i = n; i >= 1; i--)
        if (F[i] == m && a[i] < ma) {
            /// Cho them dieu kien a[i] < ma de dam bao day con truy vet la day don dieu tang dan
            /// (Neu dieu kien la day tang dan thi sua lai thanh a[i] <= ma)
            T.push_back(a[i]);
            ma = a[i];
            m--;
        }
    for (int i = T.size() - 1; i >= 0; i--)
        cout << T[i] << " ";
    cout << endl;

    cout << "- Cach 2: " << endl;
    TruyVet(k);
}