lis.cpp (4)

Bài toán

Tìm dãy con tăng (thật sự tăng) dài nhất của một dãy số.

Độ phức tạp

O(n logn)

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

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#include <vector>

using namespace std;

bool maximize(int &a, int b) {

    if (a < b)

        a = b;

    else

        return false;

    return true;

}

int n, answer = 0;

int a[1230997];

int b[1230997];

int f[1230997];

vector<int> T;

int main() {

    scanf("%d", &n);

    //for (int i=1; i<=n; i++) scanf("%d", &a[i]);

    srand(n * 1000);

    for (int i = 1; i <= n; i++) a[i] = (rand() % 100 - 10) * 10;

    for (int i = 1; i <= n; i++) printf(i == n ? "%d\n" : "%d ", a[i]);

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

        f[i] = lower_bound(b + 1, b + answer + 1, a[i]) - b;

        maximize(answer, f[i]);

        b[f[i]] = a[i];

    }

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

    int require = answer;

    for (int i = n; i >= 1; i--)

        if (f[i] == require) {

            T.push_back(a[i]);

            require--;

        }

    reverse(T.begin(), T.end());

    for (int i = 0; i < T.size(); i++)

        printf("%d ", T[i]);

    printf("\n");

}

Nhận xét

Code này đã được dùng để nộp cho một bài trên UVa và SPOJ (sau khi chỉnh sửa phần nhập input và output).