lis.cpp (2)

Bài toán

Cho một dãy số, tìm dãy tăng (tăng hẳn) dài nhất.

Độ phức tạp

O (n logn)

Code này của : Nguyễn Tiến Trung Kiên

#include <stdio.h>

int a[1230997];

int b[1230997];

int n;

int lis(const int a[], int b[]) {

    static int p[1230997];

    int r = 0, j, i, ll, rr;

    for (i = 1; i <= n; i++) {

        if (r == 0) {

            p[i] = 0;

            b[++r] = i;

        } else if (a[i] > a[b[r]]) {

            p[i] = b[r];

            b[++r] = i;

        } else {

            ll = 1, rr = r, j = (ll + rr) / 2;

            while (ll != j && j != rr) {

                if (a[b[j]] >= a[i])

                    rr = j;

                else

                    ll = j;

                j = (ll + rr) / 2;

            }

            for (j = ll; j <= rr; j++)

                if (a[b[j]] >= a[i]) {

                    p[i] = b[j - 1];

                    b[j] = i;

                    break;

                }

        }

    }

    j = b[r];

    for (i = r; i >= 1; i--) {

        b[i] = j;

        j = p[j];

    }

    return r;

}

int main() {

    //freopen("input", "r", stdin);

    int i, r;

    scanf("%d", &n);

    for (i = 1; i <= n; i++)

        scanf("%d", &a[i]);

    r = lis(a, b);

    printf("%d\n", r);

    for (i = 1; i <= r; i++)

        printf(i == r ? "%d\n" : "%d ", a[b[i]]);

}

Nhận xét

Bài này, mảng b là mảng chứa các chỉ số.

Hàm lis trả về độ dài của dãy tăng.

Kết quả cần in ra là a[b[1]], a[b[2]],...,a[b[r]]. Với r=lis(a,b), tức r là độ dài.

Đã được kiểm tra độ chính xác qua bài tập LIS trên vn.spoj.com.

Sample Input

10

7 5 5 1 5 3 3 3 5 9

Sample Output

4

1 3 5 9

Sample Input 2 (algorithm.com)

13

1 9 3 8 11 4 5 6 4 19 7 1 7

Sample Output 2

6

1 3 4 5 6 7