Cod sursa(job #1162166)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 31 martie 2014 17:51:02
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>
#include <algorithm>
#define Nmax 100005

using namespace std;

int v[Nmax],L[Nmax],poz[Nmax];

int main()
{
    int i,N,len,p;
    freopen ("scmax.in","r",stdin);
    freopen ("scmax.out","w",stdout);
    scanf("%d", &N);
    for(i=1;i<=N;++i)
        scanf("%d", &v[i]);
    L[1]=v[1]; len=1; poz[1]=1;
    for(i=2;i<=N;++i)
    {
        p=upper_bound(L+1,L+len+1,v[i])-L;
        if(L[p-1]==v[i])
            --p;
        L[p]=v[i];
        poz[i]=p;
        len=max(len,p);
    }
    printf("%d\n", len);
    p=len;
    for(i=N;i;--i)
        if(poz[i]==p)
            L[p--]=v[i];
    for(i=1;i<=len;++i)
        printf("%d ", L[i]);
    printf("\n");
    return 0;
}