LIS spoj – Dãy con tăng dài nhất (bản khó)

Nguồn đề bài http://vn.spoj.com/problems/LIS/

Đề bài LIS Spoj

Tìm dãy con tăng dài nhất, số lượng phần tử tối đa 30000. In ra số lương lớn nhất có thể

Input:
5
2 1 4 3 5

Output:
3

Link nộp bài:

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

Code Lis spoj Pascal

const fi=      '';
      fo=      '';
      maxd=    30001;
var   a:       array[0..maxd] of longint;
      l:       array[0..maxd] of integer;
      n:       longint;
      d:       longint;


procedure mofile;
var i,j:integer;
begin
     assign(input,fi);reset(input);
     assign(output,fo);rewrite(output);
end;
procedure dongfile;
begin
     close(input);close(output);
end;
procedure nhap;
var i:longint;
    f:text;
begin
    assign(f,fi); reset(f);
     readln(f,n);
     for i:=1 to n do
     read(f,a[i]);         close(f);
end;



procedure xuli;
var i,k,dau,cuoi:longint;
begin
    l[1]:=1;d:=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
                                k:=(dau+cuoi) div 2;
                                if a[l[k]]<a[i] then
                                    dau:=k+1
                                else
                                    cuoi:=k;
                            end;
                        l[dau]:=i;

                    end;
        end;
end;

procedure xuat;
begin
     write(d);
end;

begin
     nhap;
     xuli;
     xuat;
end.