Cod sursa(job #1649129)

Utilizator andreizaicescuAndrei Zaicescu andreizaicescu Data 11 martie 2016 12:39:27
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>

using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int x[100001],a[100002],n,i,j,maxi,poz,v[100003];
int rec(int poz, int k)
{
    int j;
    if(k>=1)
    {
        for(j=poz+1;j<=n;j++)
            if(x[j]==k and a[j]>a[poz])
                {if(rec(j,k-1)==1);
                    v[k]=a[poz];
                    j=n+1;
                }
    }
    else
    {
        v[k]=a[poz];
    }
    return 1;
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    x[n]=1;
    for(i=n-1;i>=1;i--)
       {
        maxi=0;
        for(j=i+1;j<=n;j++)
        if(a[i]<a[j] and x[j]>maxi)
            maxi=x[j];
        x[i]=maxi+1;
       }
    maxi=x[1];
    for(i=2;i<=n;i++)
        if(x[i]>maxi)
        {
            maxi=x[i];
            poz=i;
        }
    g<<x[poz]<<'\n';
    rec(poz,maxi-1);
    for(i=maxi-1;i>=0;i--)
        g<<v[i]<<" ";
    return 0;
}