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

const fi='';
      fo='';
      maxn=100001;
type ar=array[0..maxn] of longint;
var n,re,num,max:longint;
    a,d,e,f,inc,dec:ar;

procedure rf;
var i:longint;
begin
     assign(input,fi); reset(input);
     read(n);
     for i:=1 to n do
     begin
          read(a[i]);
          d[i]:=i;
     end;
     close(input);
end;

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 edit;
var i:longint;
begin
     a[0]:=-1;
     for i:=1 to n do
     begin
          e[d[i]]:=i;
          if a[i]=a[i-1] then d[i]:=d[i-1]
          else d[i]:=d[i-1]+1;
     end;
     max:=d[n];
end;

function getmax(x,y:longint):longint;
begin
     if x>y then getmax:=x else getmax:=y;
end;

procedure add(x,t:longint);
begin
     while x<=max do
     begin
          if f[x]<t then f[x]:=t 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:=getmax(r,f[x]);
          x:=x-x and (-x);
     end;
     calc:=r;
end;

procedure pr;
var i,x,t:longint;
begin
     sort(1,n);
     edit;
     for i:=1 to n do
     begin
          x:=d[e[i]];
          t:=calc(x-1);
          inc[i]:=t+1;
          add(x,t+1);
     end;
     fillchar(f,sizeof(f),0);
     for i:=n downto 1 do
     begin
          x:=d[e[i]];
          t:=calc(x-1);
          dec[i]:=t+1;
          add(x,t+1);
     end;
     re:=0;
     for i:=1 to n do
     begin
          if inc[i]<dec[i] then t:=inc[i] shl 1-1
          else t:=dec[i] shl 1-1;
          if t>re then re:=t;
     end;
end;

procedure wf;
begin
     assign(output,fo); rewrite(output);
     writeln(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

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

#define N 100000

int x[N+1], a[N], n, lis[N], lds[N];

void LIS() {
    fill(x+1, x+n+1, INT_MAX);
    x[0] = INT_MIN; int maxlen = 0;
    for(int i = 0; i < n; ++i) {
        int p = lower_bound(x, x+maxlen+1, a[i]) - x;
        lis[i] = p;
        maxlen = max(maxlen, p);
        x[p] = min(x[p], a[i]);
    }
}

void LDS() {
    fill(x+1, x+n+1, INT_MAX);
    x[0] = INT_MIN; int maxlen = 0;
    for(int i = n-1; i >= 0; --i) {
        int p = lower_bound(x, x+maxlen+1, a[i]) - x;
        lds[i] = p;
        maxlen = max(maxlen, p);
        x[p] = min(x[p], a[i]);
    }
}

bool enter() {
    if(scanf("%d", &n) == EOF) return 0;
    for(int i = 0; i < n; ++i) scanf("%d", a+i);
    return 1;
}

void print() {
    int res = 0;
    for(int i = 0; i < n; ++i) res = max(res, 2*min(lis[i], lds[i]) - 1);
    printf("%d\n", res);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    while(enter()) {
        LIS(); LDS();
        print();
    }
    return 0;
}

Code mẫu của ladpro98

program spseq;
uses    math;
const   fi='';
        maxN=100005;
var     a,b,lis,lis2,f:array[0..maxn] of longint;
        n,res,i:longint;
procedure input;
var     f:text;
        i:longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,n);
        for i:=1 to n do
        read(f,a[i]);
        close(f);
        b:=a;
end;

function findmax(r,key:longint):longint;
var     l,m,k:longint;
begin
        l:=0;k:=0;
        while l<=r do
        begin
                m:=(l+r) shr 1;
                if a[f[m]]<key then
                begin
                        k:=m;
                        l:=m+1;
                end
                else
                r:=m-1;
        end;
        exit(k);
end;

procedure dp;
var     i,d,x:longint;
begin

        lis[1]:=1;
        f[1]:=1;
        d:=1;
        for i:=2 to n do
        begin
                if a[i]<a[f[1]] then
                begin
                        lis[i]:=1;
                        f[1]:=i
                end
                else
                begin
                        if a[i]>a[f[d]] then
                        begin
                                inc(d);
                                f[d]:=i;
                                lis[i]:=d;
                        end
                        else
                        begin
                                X:=findmax(d,a[i])+1;
                                f[x]:=i;
                                lis[i]:=x;
                        end;
                end;
        end;
end;

begin
        input;
        dp;
        for i:=1 to n do lis2[i]:=lis[n-i+1];
        for i:=1 to n do a[i]:=b[n-i+1];
        dp;
        for i:=1 to n do
        res:=max(res,min(lis[i],lis2[i])*2-1);
        write(res);
end.

Code mẫu của RR

//Written by RR

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       100111;

var
  f1,f2         :       text;
  n,s           :       longint;
  a,ind,c       :       array[1..MAXN] of longint;
  f,g           :       array[1..MAXN] of longint;
  ln            :       array[1..MAXN] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i:longint;
    begin
      read(f1,n);
      for i:=1 to n do
        read(f1,a[i]);
    end;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort(l,r:longint);
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=c[l+random(r-l+1)];
      repeat
        while c[i]<mid do inc(i);
        while c[j]>mid do dec(j);
        if i<=j then
          begin
            swap(c[i],c[j]);
            swap(ind[i],ind[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<J then sort(l,j);
    end;

procedure RR;
    var
      i:longint;
    begin
      for i:=1 to n do
        begin
          c[i]:=a[i];
          ind[i]:=i;
        end;
      sort(1,n);
      a[ind[1]]:=1; s:=1;
      for i:=2 to n do
        begin
          if c[i]>c[s] then
            begin
              inc(s);
              c[s]:=c[i];
            end;
          a[ind[i]]:=s;
        end;
    end;

function get(u:longint):longint;
    var
      v:longint;
    begin
      if (u<=0) then exit(0);
      v:=u-u and (-u);
      exit(max(ln[u],get(v)));
    end;

procedure update(u,k:longint);
    var
      v:longint;
    begin
      ln[u]:=max(ln[u],k);
      v:=u+u and (-u);
      if v<=s then update(v,k);
    end;

procedure solve;
    var
      i,res:longint;
    begin
      for i:=1 to n do
        begin
          f[i]:=get(a[i]-1)+1;
          update(a[i],f[i]);
        end;
      fillchar(ln,sizeof(ln),0);
      for i:=n downto 1 do
        begin
          g[i]:=get(a[i]-1)+1;
          update(a[i],g[i]);
        end;

      res:=0;
      for i:=1 to n do
          res:=max(res,min(f[i],g[i])*2-1);
      writeln(f2,res);
    end;

begin
  openF;
  inp;
  RR;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
//#include <conio.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define DOWN(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a) REP(i,0,a);
#define pb  push_back
#define INF 1000000000
#define VI vector<int>
#define VVI vector<VI>
//ham
template <class T>  //so ko am
T gcd(T a, T b){if(b==0) return abs(a); else return gcd(b,a%b);}
template <class T>  
T lcm(T a, T b){ return a/gcd(a,b) *b;}

int n,a[100005],b[100005],l[100005],r[100005],m[100005],dis;
int main()
{
    //freopen("SPSEQ.IN", "rt", stdin);
    //freopen("SPSEQ.OUT", "wt", stdout);              
    scanf("%d",&n);
    REP(i,0,n-1)
    {
        scanf("%d",&a[i]);
        //cout<<a[i]<<" ";
        b[n-1-i]=a[i];
    }
   // cout<<endl;
    //Tinh left
    REP(i,0,n) m[i]=100005; //fill;
    dis=1;
    m[1]=a[0];
    l[0]=1;
    REP(i,1,n-1)
    {
        if(m[1]>=a[i]) {
            l[i]=1;
            m[1]=a[i];
            continue;
        }
        if(m[dis]<a[i])
        {
            l[i]=dis+1;
            m[dis+1]=a[i];
            dis++;
            continue;
        }

        int first=1,last=dis;
        while(last-1>first)
        {
            int mid=(first+last)/2;
            if(m[mid]<a[i])
                first=mid;
            else  //m[mid]>=a[i]
            {
                last=mid;    
            } 
        }
        l[i]=last;
        m[last]=a[i];

    }
    /*
    REP(i,0,n-1)
        cout<<i<<" "<<l[i]<<endl;
        */
    //return 0;
        //cout<<"Xong +_________________+"<<endl<<endl;
    //Tinh right
    REP(i,0,n) m[i]=100005; //fill;
    dis=1;
    m[1]=b[0];
    r[n-1]=1;
    REP(i,1,n-1)
    {
        if(m[1]>=b[i]) {
            r[n-1-i]=1;
            m[1]=b[i];
            continue;
        }
        if(m[dis]<b[i])
        {
            r[n-1-i]=dis+1;
            m[dis+1]=b[i];
            dis++;
            continue;
        }

        int first=1,last=dis;
        while(last-1>first)
        {
            int mid=(first+last)/2;
            if(m[mid]<b[i])
                first=mid;
            else  //m[mid]>=a[i]
            {
                last=mid;    
            } 
        }
        r[n-1-i]=last;
        m[last]=b[i];

    }
    /*
    REP(i,0,n-1)
        cout<<i<<" "<<r[i]<<endl;
        */
    int maxDis=-1;
    REP(i,0,n-1)
    {
        maxDis=max(maxDis,min(l[i],r[i]));    
    }

    if(maxDis==0) cout<<"0";
    else 
        cout<<2*maxDis-1;
}

Code mẫu của ll931110

{$MODE DELPHI}
program SPSEQ;
const
  input  = '';
  output = '';
  maxn = 100000;
var
  a,b,d,pos: array[1..maxn] of integer;
  L,L1,L2,t: array[1..maxn] of integer;
  n: integer;
  res: integer;

procedure init;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n);
  for i := 1 to n do
    begin
      read(f, d[i]);
      pos[i] := i;
    end;

  close(f);
end;

procedure swap(var x,y: integer);
var
  z: integer;
begin
  z := x;  x := y;  y := z;
end;

procedure swapint(i,j: integer);
begin
  swap(d[i],d[j]);
  swap(pos[i],pos[j]);
end;

procedure quicksort;

  procedure par(l,h: integer);
  var
    i,j,p: integer;
  begin
    if l >= h then exit;
    i := l;  j := h;  p := d[random(h - l + 1) + l];

    repeat
      while (d[i] < p) do inc(i);
      while (d[j] > p) do dec(j);

      if i <= j then
        begin
          if i < j then swapint(i,j);
          inc(i);
          dec(j);
        end;
    until i > j;

    par(l,j);
    par(i,h);
  end;

var
  i,c: integer;
begin
  par(1,n);
  c := 1;
  b[pos[1]] := 1;
  for i := 2 to n do
    begin
      if d[i] > d[i - 1] then inc(c);
      b[pos[i]] := c;
    end;
end;

procedure update(x,m: integer);
begin
  while x <= maxn do
    begin
      if t[x] < m then t[x] := m;
      x := x + (x and -x);
    end;
end;

function calc(x: integer): integer;
var
  r: integer;
begin
  r := 0;
  while x > 0 do
    begin
      if r < t[x] then r := t[x];
      x := x - (x and -x);
    end;
  calc := r;
end;

procedure optimize;
var
  i: integer;
begin
  fillchar(t, sizeof(t), 0);

  update(1,1);
  for i := 1 to n do
    begin
      L[i] := calc(a[i]);
      update(a[i] + 1,L[i] + 1);
    end;
end;

procedure solve;
var
  i,min: integer;
begin
  for i := 1 to n do a[i] := b[i];
  optimize;
  L1 := L;

  for i := 1 to n do a[i] := b[n + 1 - i];
  optimize;
  L2 := L;

  res := 0;
  for i := 1 to n do
    begin
      if L1[i] > L2[n + 1 - i] then min := L2[n + 1 - i] else min := L1[i];
      if res < min then res := min;
    end;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, 2 * res - 1);
  close(f);
end;

begin
  init;
  quicksort;
  solve;
  printresult;
end.

Code mẫu của khuc_tuan

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

int n;
int a[100010], f1[100010], f2[100010], g[100010];

void process( int * a, int * f) {
    int ng = 0;
    for(int i=0;i<n;++i) {
        int id = lower_bound( g, g + ng, a[i]) - g;
        if(id == ng) ++ng;
        g[id] = a[i];
        f[i] = ng;
    }
}

int main() {
    scanf("%d", &n);
    for(int i=0;i<n;++i) scanf("%d", a+i);
    process( a, f1);
    reverse( a, a + n);
    process( a, f2);
    int best = 0;
    for(int i=0;i<n;++i) best = max( best, min(f2[i], f1[n-i-1]) * 2 - 1);
    cout << best << endl;
    return 0;
}