Cod sursa(job #1188499)

Utilizator armandpredaPreda Armand armandpreda Data 19 mai 2014 19:17:55
Problema Subsir crescator maximal Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>
#define LIM 100000

using namespace std;

int v[LIM+10],nr[LIM+10],tata[LIM+10];
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    int n,i,max,poz;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",v+i);
    nr[n]=1;
    for(i=n-1;i>=1;--i)
    {
        max=0;
        for(int j=i+1;j<=n;++j)
            if(nr[j]>max and v[i]<v[j])
                max=nr[j],poz=j;
        nr[i]=max+1;
        tata[i]=poz;
        if(max=0)
            tata[i]=0;
    }
    max=0;
    for(i=1;i<=n;++i)
        if(nr[i]>max)
                max=nr[i],poz=i;
    printf("%d\n",max);
    printf("%d ",v[poz]);
    while(tata[poz]!=0)
    {
        poz=tata[poz];
        printf("%d ",v[poz]);
    }
    return 0;
}