QBDIVSEQ - Chia dãy
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
Program QBDIVSEQ;
Const
input = '';
output = '';
maxn = 100000;
Var
a,s: array[1..maxn] of integer;
n,k: integer;
Procedure init;
Var
f: text;
i: integer;
Begin
Assign(f, input);
Reset(f);
Readln(f, n);
For i:= 1 to n do readln(f, a[i]);
Close(f);
End;
Procedure update(i: integer);
Var
inf,sup,med,r: integer;
Begin
If s[k] > a[i] then
Begin
inc(k);
s[k]:= a[i];
exit;
End;
inf:= 1;
sup:= k;
r:= 0;
Repeat
med:= (inf + sup) div 2;
If s[med] = a[i] then exit;
If s[med] > a[i] then inf:= med + 1 else
Begin
r:= med;
sup:= med - 1;
End;
Until inf > sup;
s[r]:= a[i];
End;
Procedure optimize;
Var
i: integer;
Begin
k:= 1;
s[1]:= a[1];
For i:= 2 to n do update(i);
End;
Procedure printresult;
Var
f: text;
Begin
Assign(f, output);
Rewrite(f);
Writeln(f, k);
Close(f);
End;
Begin
init;
optimize;
printresult;
End.