Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

uses math;
var maxc,n,re,i:longint;
    a,b,f,d:array[1..30000] of longint;

procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
        i:=l; j:=r; x:=a[(i+j) shr 1];
        repeat
                while a[i]<x do i:=i+1;
                while a[j]>x do j:=j-1;
                if i<=j then
                begin
                        y:=a[i]; a[i]:=a[j]; a[j]:=y;
                        y:=d[i]; d[i]:=d[j]; d[j]:=y;
                        i:=i+1; j:=j-1;
                end;
        until i>j;
        if i<r then sort(i,r);
        if l<j then sort(l,j);
end;

procedure add(x,v:longint);
begin
        while x<=maxc do
        begin
                if v>f[x] then f[x]:=v
                else exit;
                x:=x+x and (-x);
        end;
end;

function calc(x:longint):longint;
var r:longint;
begin
        r:=0;
        while x>0 do
        begin
                r:=max(r,f[x]);
                x:=x-x and (-x);
        end;
        calc:=r;
end;

begin
        read(n);
        for i:=1 to n do
        begin
                read(a[i]);
                d[i]:=i;
        end;
        sort(1,n);
        maxc:=1; b[d[1]]:=1;
        for i:=2 to n do
        begin
                if a[i]>a[maxc] then
                begin
                        inc(maxc);
                        a[maxc]:=a[i];
                end;
                b[d[i]]:=maxc;
        end;
        for i:=1 to n do
            add(b[i],calc(b[i]-1)+1);
        writeln(calc(maxc));
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 30000+2;
int n, a[N], lst[N]; 

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%d", a+i);
    int maxlen = 0;
    for(int i = 0; i < n; ++i) {
        int dp = lower_bound(lst, lst+maxlen, a[i]) - lst;
        if(dp == maxlen) ++maxlen, lst[dp] = a[i];
        else lst[dp] = min(lst[dp], a[i]);
    }
    printf("%d\n", maxlen);
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

int main()
{
    multiset <int> S;
    multiset <int> :: iterator it;
    int n, ai;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &ai);
        S.insert(ai);
        it = S.lower_bound(ai);
        it++;
        if (it != S.end()) S.erase(it);
    }
    printf("%d", S.size());
    return 0;
}

Code mẫu của RR

uses math;
var
  f,a,h:array[1..30111] of longint;
  res,n,i,top,u:longint;

function find(val:longint):longint;
    var
      res,l,r,mid:longint;
    begin
      res:=0; l:=1; r:=top;
      while (l<=r) do
        begin
          mid:=(l+r) shr 1;
          if h[mid]<val then
            begin
              res:=mid;
              l:=mid+1;
            end
          else r:=mid-1;
        end;
      exit(res);
    end;

begin
  read(n);
  for i:=1 to n do read(a[i]);

  h[1]:=a[1]; top:=1; f[1]:=1;
  for i:=2 to n do
    if a[i]>h[top] then
      begin
        inc(top);
        h[top]:=a[i]; f[i]:=top;
      end
    else if a[i]<h[1] then
      begin
        h[1]:=a[i];
        f[i]:=1;
      end
    else
      begin
        u:=find(a[i]);
        f[i]:=u+1;
        h[u+1]:=min(h[u+1],a[i]);
      end;

  res:=1;
  for i:=1 to n do
    res:=max(res,f[i]);
  writeln(res);
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int main()
{
    int n,f[100001],a[100001],t;
    scanf("%d",&n);
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    t = 1;
    f[1] = a[1];
    for(int i = 2;i<=n;i++)
    {
        if(a[i]>f[t])
        {
            t++;
            f[t] = a[i];
        }
        else if(a[i]<=f[1]) f[1] = a[i];
        else
        {
            int u = 1,v = t,r;
            while(v-u>1)
            {
                r = (u+v)/2;
                if(a[i]>f[r])
                    u = r;
                else v = r;
            }

        f[v] = a[i];
        }
    }
    printf("%d",t);
    //getch();
}

Code mẫu của ll931110

Program LIS;
        Const
                input  = '';
                output = '';
        Var
                a,L,start: array[0..30001] of longint;
                      n,m: longint;

Procedure enter;
          Var
                i: longint;
                f: text;
          Begin
                Assign(f, input);
                        Reset(f);
                                Readln(f, n);
                                For i:= 1 to n do read(f, a[i]);
                Close(f);
          End;

Procedure init;
          Begin
                a[0]:= low(longint);
                a[n + 1]:= high(longint);

                m:= 1;
                L[n + 1]:= 1;
                Start[1]:= n + 1;
          End;

Function Find(i: longint): longint;
         Var
                inf,sup,med,j: longint;
         Begin
                inf:= 1;
                sup:= m + 1;

                Repeat
                        med:= (inf + sup) div 2;
                        j:= start[med];

                        If a[j] > a[i] then inf:= med else sup:= med;
                Until inf + 1 = sup;

                Find:= start[inf];
         End;

Procedure optimize;
          Var
                i,j,k: longint;
          Begin
                For i:= n downto 0 do
                        Begin
                                j:= Find(i);
                                k:= L[j] + 1;

                                If m < k then
                                        Begin
                                                m:= k;
                                                Start[k]:= i;
                                        End
                           else if a[start[k]] < a[i] then start[k]:= i;

                           L[i]:= k;
                         End;
          End;

Procedure printresult;
          Var
                f: text;
          Begin
                Assign(f, output);
                        Rewrite(f);
                        Writeln(f, m - 2);
                Close(f);
          End;

Begin
        enter;
        init;
        optimize;
        printresult;
End.

Code mẫu của skyvn97

#include<stdio.h>
using namespace std;

const int maxn = 3e4 + 4;
long int n, a [maxn], lis [maxn], t [maxn], p;

int main (void) 
{
    scanf ("%d", &n);
    a [0] = -1e9;
    a [n + 1] = 1e9;

    for (int i = 1; i <= n + 1; ++i) {
        if (i <= n) scanf ("%ld", &a [i]);
        int l = 0, r = p;
        while (l < r) {
            int m = (l + r + 1) / 2;
            if (a [t [m]] < a [i]) l = m;
            else r = m - 1;
        }
        lis [i] = l + 1;
        if (lis [i] > p) t [++p] = i;
        else if (a [i] < a [t [lis [i]]]) t [lis [i]] = i;
    }
    printf ("%ld\n", lis [n + 1] - 1);
    return 0;
}