DP, LIS.

Ý tưởng

• Với từng ~a[i]~, giả sử ta chọn ~a[i]~ làm phần tử đầu tiên được thêm để tạo thành dãy B, ta rút ra nhận xét như sau:

• Các phần tử được thêm vào dãy ~B~ bằng cách thêm vào đầu, ta thêm lần lượt và vẫn giữ nguyên trình tự khi nằm trên dãy ~A~. Nhận ra rằng các phần tử đó tạo ra dãy con giảm dài nhất có phần tử đầu tiên là ~a[i]~ . Vì là dãy giảm dài nhất nên khi ta thêm lần lượt vào dãy ~B~ bằng cách thêm vào đầu thì dãy B vẫn tăng dần (thỏa mãn tính chất, và các số được thêm vào luôn tăng, dài nhất).

• Tương tự với các phần tử được thêm vào dãy ~B~ Bằng cách thêm vào đuôi. Nhận ra rằng các phần tử đó tạo ra dãy con tăng dài nhất có phần tử đầu tiên là ~a[i]~ .

--> Với từng ~a[i]~ ta chỉ cần tìm các dãy tăng hoặc giảm ngặt bắt đầu bằng ~a[i]~ và kết quả là giá trị lớn nhất giữa tổng hai độ dài trừ đi ~1~ vì ~a[i]~ lặp lại hai lần.

Đọc thêm về cách tìm LIS trong ~O(nlogn)~ tại đây

Code mẫu

#include <bits/stdc++.h>

using namespace std;

int n;
int a[100001];

int f[200001], g[200001];
int bit1[200001], bit2[200001];

void upd1(int x, int val) {
    for (; x > 0; x -= x & (-x))
        bit1[x] = max(bit1[x], val);
}

void upd2(int x, int val) {
    for (; x <= n; x += x & (-x))
        bit2[x] = max(bit2[x], val);
}

int query1(int x) {
    int ans = 0;
    for (; x <= n; x += x & (-x))
        ans = max(ans, bit1[x]);
    return ans;
}

int query2(int x) {
    int ans = 0;
    for (; x > 0; x -= x & (-x))
        ans = max(ans, bit2[x]);
    return ans;
}


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    vector<int> val;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        val.push_back(a[i]);
    }
    sort(val.begin(), val.end());

    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1;

    for (int i = n; i >= 1; i--) {
        f[i] = 1 + query1(a[i] + 1);
        g[i] = 1 + query2(a[i] - 1);
        upd1(a[i], f[i]); upd2(a[i], g[i]);
    }       

    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, f[i] + g[i] - 1);
    cout << ans;
}