Cod sursa(job #1382486)

Utilizator teoceltareconstantin teodor teoceltare Data 9 martie 2015 09:09:34
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,v[100001],c[100001],d[100001],max1=0;
void citire()
{
    fin>>n;
    for(int a=1;a<=n;a++)
    {
        fin>>v[a];
    }
}
void fct(int x)
{
    for(int a=x-1;a>=1;a--)
    {
        if(c[a]<c[x]+1 and v[a]<=v[x])
        {
            c[a]=c[x]+1;
            if(c[a]>c[max1]) max1=a;
            d[a]=x;
            fct(a);
        }
    }
}
int main()
{
    citire();
    max1=n;
    for(int a1=n;a1>=1;a1--)
    {
        if(c[a1]==0)
        {
            c[a1]=1;
            fct(a1);
        }
    }
    fout<<c[max1]<<endl;
    while(max1)
    {
        fout<<v[max1]<<" ";
        max1=d[max1];
    }
}