Cod sursa(job #251021)

Utilizator crawlerPuni Andrei Paul crawler Data 1 februarie 2009 17:11:20
Problema Subsir crescator maximal Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>

#define Nmax 100100

int a[Nmax], b[Nmax], n, max;

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    
    scanf("%d", &n);
    
    for (int i=1;i<=n;++i)
    scanf("%d", a+i);
    
    max = 1;
    b[1] = 1;    
    
    for (int i=2;i<=n;++i)
    {
        int tmp=0;
        for(int x=max;x>0;x/=2)
        if (tmp+x <= max)
        if (a[b[tmp+x]] < a[i])
        tmp+=x;        
        while (a[b[tmp]] < a[i] && tmp<=max) ++tmp;
        if (a[b[tmp]] > a[i]) b[tmp] = i;
        if (tmp > max) b[++max] = i;
    }
    
    printf("%d\n", max);
    
    for (int i=1;i<=max;++i) printf("%d ", a[b[i]]); printf("\n");    
    
    return 0;    
}