Cod sursa(job #1512987)

Utilizator EberardoVladianu Cosmin Eberardo Data 28 octombrie 2015 21:11:35
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n;
int v[100001],best[100001],t[100001];
void citire()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
}
void caut(int i)
{
    int j;
    int maxi=0,poz=0;
    for(j=i-1;j>=1;j--)
    {
        if(v[i]>v[j])
        {
            if(best[j]>maxi)
            {
                maxi=best[j];
                poz=j;
            }
        }
    }
    t[i]=poz;
    best[i]=maxi+1;
}
void afis(int nod)
{
    int tata=t[nod];
    if(nod==0)
        return;
    afis(tata);
    fout<<v[nod]<<' ';

}
void rez()
{
    int i;
    int maxi=0,poz;
    for(i=1;i<=n;i++)
    {
        caut(i);
        if(best[i]>maxi)
        {
            maxi=best[i];
            poz=i;
        }
    }
    fout<<maxi<<'\n';
    afis(poz);
}
int main()
{
    citire();
    rez();
    return 0;
}