Cod sursa(job #362938)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 11 noiembrie 2009 13:00:55
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>

using namespace std;

int l[100002],a[100002];
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    l[1]=1;
    int max=1;
    int poz;

    for(int i=2;i<=n;i++)
    {
        for(int j=i-1;j>0;j--)
            if(a[i]>a[j])
                if(l[i]<l[j]+1)l[i]=l[j]+1;
        if(l[i]==0)l[i]++;
        if(l[i]>max)max=l[i],poz=i;
    }
    cout<<max<<endl;
    int k[100002];
    int cacat=max;
    for(int i=poz;i>0&&max;i--)
        if(l[i]==max)k[max--]=a[i];
    for(int i=1;i<=cacat;i++)
        cout<<k[i]<<" ";

    return 0;
}