Cod sursa(job #911637)

Utilizator ucnahHancu Andrei ucnah Data 11 martie 2013 20:02:17
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>

using namespace std;
int n,a[100010],pas[100010];
void afisare(int nr,int loc)
{
    printf("%d ",a[loc]);
    for(int i=loc+1;i<=n;i++)
    if(pas[i]==nr-1 && a[i]>a[loc])
    {
        nr=pas[i];
        loc=i;
        printf("%d ",a[i]);
    }
}
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]);
    pas[n]=1;
    int maxim=0,ok=0,aux=-1,loc;
    for(int i=n;i>=1;i--)
    {
        maxim=0;ok=0;
        for(int j=i+1;j<=n;j++)
        {
            if(pas[j]>maxim && a[i]<a[j])
            {
                maxim=pas[j];
                pas[i]=1+maxim;
                if(aux<pas[i])
                {
                    aux=pas[i];
                    loc=i;
                }
                ok=1;
            }
            if(ok==0)
                pas[i]=1;
        }
    }
    printf("%d\n",aux);
    afisare(aux,loc);
    return 0;
}