Bài toán
Tìm dãy con tăng dài nhất của một dãy số.
Dãy con của một dãy là dãy mà có thể đạt được bằng cách xoá đi một số phần tử trong dãy ban đầu. Dãy rỗng và dãy ban đầu cũng là dãy con của dãy ban đầu.
Ở bài này, ta tìm dãy tăng, tức là phần tử đứng sau phải lớn hơn hẳn phần tử trước.
Độ phức tạp
O(n logn)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define N 100005
int n, a[N], F[N];
int m, b[N];
int main() {
// array a, length n
while (scanf("%d", &a[n + 1]) > 0) n++;
// array b, length m, in increasing order
for (int i = 1; i <= n; i++) {
F[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
m = max(m, F[i]);
b[F[i]] = a[i];
}
// m is also max(F)
printf("%d\n-\n", m);
int Expected = m;
vector<int> T;
// add m elements from a into T
for (int i = n; i >= 1; i--) {
if (F[i] == Expected) {
T.push_back(a[i]);
Expected--;
}
}
// output T in reversed order
for (int i = T.size() - 1; i >= 0; i--)
printf("%d\n", T[i]);
}
Nhận xét
Code này đã được dùng để nộp cho một bài trên UVa.
Mô tả
int n, a[]
Dãy a, độ dài n, là dãy ban đầu.
int F[]
Dãy F, độ dài n, F[i] có ý nghĩa: nếu phải chọn phần tử a[i] thì dãy con tăng dài nhất kết thúc tại i có độ dài bao nhiêu.
int m, b[]
Dãy b, độ dài m, là một dãy phụ chứa các phần tử "tiềm năng". Khi cho i chạy đến vị trí i, nếu i được chọn, phần tử a[i] sẽ được nối theo sau một phần tử tiềm năng. Nếu phần tử x được đặt vào vị trí b[k] (b[k]=x) thì phải có F[x]=k. Chi tiết hơn, ta có thể hiểu b[k] là một dãy chứa các phần tử x mà F[x]=k, tuy nhiên, trong các phần tử đó, ta chỉ cần giữ lại phần tử bé nhất, các phần tử khác không có tác dụng, thế nên phần tử được giữ lại ta gọi là phần tử tiềm năng. Ngoài ra, b còn là một dãy tăng.
Khi chạy i, ta sẽ duy trì dãy b (dãy các phần tử tiềm năng), vì b chỉ chứa các phần tử tiềm năng đồng thời là một dãy tăng, ta có thể chặt nhị phân trên b. Giả sử b[k] < a[i], khi đó a[i] có thể kết hợp với b[k] (nối theo sau b[k]). Ta sẽ chọn k lớn nhất, sau đó gán F[i]=k+1. Vì k là vị trí cuối cùng trên mảng b mà b[k] < a[i] nên k+1 chính là vị trí đầu tiên trên mảng b mà b[k+1] >= a[i]. Sau khi tính được F[i], ta cập nhật mảng b (b[F[i]]=a[i]).
Tham khảo
http://uva.onlinejudge.org/external/4/481.html