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.

Download