LIS – Dãy con tăng dài nhất

Đề bài: Tìm độ dài dãy con tăng dài nhất của dãy số A có N phần tử

Code C++:

#include <iostream>
using namespace std;

const int MAXN = 1e5 + 5;

int n, a[MAXN], h[MAXN];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    int L = 1;
    h[1] = 1;
    for(int i = 2; i <= n; i++) {
        int lo = 1, hi = L;
        while(lo <= hi) {
            int mi = (lo + hi) / 2;
            if (a[h[mi]] < a[i]) lo = mi + 1;
            else hi = mi - 1;
        }
        h[lo] = i;
        L = max(L, lo);
    }
    
    cout << L;
    
    return 0;
}

Độ phức tạp: O(NlogL), với L là độ dài của dãy con tăng dài nhất.

Lưu ý: Bài này đã được dùng để nộp bài LIS trên SPOJ (http://vn.spoj.com/problems/LIS/)

Ghi chú:
– Sau khi ra khỏi vòng lặp tìm kiếm nhị phân, thì lo là vị trí của phần tử cần được thay thế.
– Lúc này, h[1] đến h[lo] sẽ là index của các phần tử trong mảng a tạo thành dãy con dài nhất kết thúc ở a[i].
– Từ tính chất này, chúng ta có thể in được dãy con tăng dài nhất bằng cách sử dụng mảng truy vết trace[i] với ý nghĩa: trace[i] là index của phần tử ở ngay trước a[i] trong dãy con tăng dài nhất kết thúc ở a[i]. Sau khi ra khỏi vòng lặp while, trace[i] = lo – 1;

Happy coding,

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s