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