SPSEQ - Sequences

Tác giả: ladpro98

Ngôn ngữ: Pascal

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.

Download