Cod sursa(job #858668)

Utilizator ucnahHancu Andrei ucnah Data 19 ianuarie 2013 10:18:18
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>

using namespace std;
int a[100000],lg[100000],n;
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]);
    lg[n]=1;
    for(int i=n;i>=1;i--)
    {
        int max=0,ok=0;
        for(int j=i+1;j<=n;j++)
        {
            if(lg[j]>max && a[i]<a[j])
            {
                max=lg[j];
                lg[i]=1+max;
                ok=1;
            }
            if(ok==0)
                lg[i]=1;
        }
    }
    int max=0,maxi=-1;
    for(int i=1;i<=n;i++)
        if(lg[i]>max)
        {
            max=lg[i];
            maxi=i;
        }
    printf("%d\n",max);
    printf("%d ",a[maxi]);
    int ok=1;
    for(int i=maxi;i<=n-1;i++)
    {
        for(int j=maxi+1;j<=n;j++)
        {
            if(lg[i]-1==lg[j] && a[i]<a[j])
            {
                printf("%d ",a[j]);
                if(lg[j]==1)
                    ok=0;
                break;
            }
        }
        if(ok==0)
            break;
    }
    return 0;
}