Cod sursa(job #356821)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 16 octombrie 2009 19:10:12
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <stdio.h>

using namespace std;

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    int a[100001],l[100001],n,m;
    int max,i,j;
    scanf("%ld",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);

    l[n-1]=1;

    for(i=n-2;i>=0;i--)
    {
        for(j=i+1,max=0;j<n;j++)
            if(a[j]>a[i])
                if(max<l[j])
                    max=l[j];
        l[i]=1+max;
    }

    for(max=0,i=0;i<n;i++)
        if(max<l[i])max=l[i],m=i;

    printf("%d\n%d",max,a[m]);
    while(m<n&&l[m]!=1)
    {
        i=m+1;
        while(!(l[m]-1==l[i]&&a[m]<a[i]))
            i++;
        printf(" %d",a[i]);
        m=i;
    }

    return 0;
}