Cod sursa(job #1393216)

Utilizator andreib98Borza Andrei andreib98 Data 19 martie 2015 10:40:03
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#define NMax 100001
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,a[NMax],c[NMax],tata[NMax],i,j,ma,y;
void afisare(int x)
{
    if(tata[x]==0) fout<<a[x]<<" ";
    else
    {
        fout<<a[x]<<" ";
        afisare(tata[x]);
    }
};
int main()
{
fin>>n;
for(i=1;i<=n;i++)
    fin>>a[i];
c[n]=1;
tata[n]=0;
for(i=n-1;i>=1;i--)
{
    c[i]=1;
    tata[i]=0;
    for(j=i+1;j<=n;j++)
    {
        if(a[i]<a[j]&&c[j]+1>c[i])
        {
            c[i]=c[j]+1;
            tata[i]=j;
        }
    }
    if(c[i]>ma)
    {
        ma=c[i];
        y=i;
    }
}
fout<<ma<<"\n";
afisare(y);

    return 0;
}