LIQ - Dãy con tăng dài nhất ( bản dễ )

Tác giả: ladpro98

Ngôn ngữ: Pascal

program daycontang;
const   fi = '';
        fo = '';
var     mang,f: array[0..30001] of longint;
        i,t,n:longint;
        inp,oup:text;
function find(i,j,x:longint):longint;
var     l,r,m,k:longint;
begin
        l:=i;r:=j;
        while l<=r do
           begin
              m:=(l+r) div 2;
              if mang[f[m]]<mang[x] then
                  begin
                      k:=m;
                      l:=m+1;
                  end
              else  r:=m-1;
           end;
        exit(k);
end;

procedure input;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do read(inp,mang[i]);
        close(inp);
end;

procedure output;
begin
        assign(oup,fo);
        rewrite(oup);
        write(oup,t);
        close(oup);
end;

begin
        input;
        f[1]:=1;
        t:=1;
        for i:=2 to n do
        begin
                if mang[i]<mang[f[1]] then f[1]:=i
                else if mang[i]>mang[f[t]] then
                begin
                        inc(t);
                        f[t]:=i;
                end
                else
                begin
                        f[find(1,t,i)+1]:=i;
                end;
        end;

        output;
end.

Download