Cod sursa(job #1145168)

Utilizator MacWonkMihai Alexandru Cosmin MacWonk Data 17 martie 2014 22:10:42
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
using namespace std;
int a[100001];
int Nr[100001];
int lgmax,n,i,j;
void scmax()
{
    Nr[n]=1;
    for(i=n-1;i>=1;--i)
    {
        Nr[i]=1;
        for(j=i+1;j<=n;++j)
        {
            if(a[j]>a[i]&&Nr[j]+1>Nr[i])
            {
                Nr[i]=Nr[j]+1;
                if(Nr[i]>lgmax) lgmax=Nr[i];
            }
        }
    }
}
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&a[i]);
    scmax();
    printf("%d\n",lgmax);
    for(i=1;i<=n&&lgmax>0;++i)
    {
        if(Nr[i]==lgmax)
        {
            printf("%d ",a[i]);
            --lgmax;
        }
    }
    return 0;
}