Đề bài:

• http://vn.spoj.com/problems/LIS/

Thuật toán:

• for lồng với chặt nhị phân mất tốc độ O(n)log(n)

• các bạn xem code thắc mắc đâu thì hỏi thêm nha

Code:

• (xem code)

program         LIS;
var     a,l:array[1..30000] of longint;
        d,i,dau,cuoi,mid,n:longint;
begin
        readln(n);
        for i:=1 to n do read(a[i]);
        d:=1;
        l[1]:=1;
        for i:=2 to n do
                begin
                        if a[i]>a[l[d]] then
                                begin
                                        inc(d);
                                        l[d]:=i;
                                end
                        else
                                begin
                                        dau:=1;
                                        cuoi:=d;
                                        while dau <= cuoi do
                                                begin
                                                        mid:=(dau+cuoi) div 2;
                                                        if a[i]>a[l[mid]] then dau:=mid+1
                                                        else cuoi:=mid-1;
                                                end;
                                        l[dau]:=i;
                                end;
                end;
        write(d);
end.