Cod sursa(job #358709)

Utilizator edy_3dzEdy 3dz edy_3dz Data 24 octombrie 2009 10:29:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>

using namespace std;

ofstream fout("scmax.out");

int i,n;
int a[100001],l[100001],t[100001];

void afish(int);

int main()
{
    ifstream f("scmax.in");
    f>>n;
    for (i=1;i<=n;i++)
     f>>a[i];
    f.close();
    l[1]=1;
    t[1]=0;
    int max=1,j,g=1;
    for(i=2;i<=n;i++)
    {
        int maxim=0,k=0;
        for(j=1;j<i;j++)
        {
            if(a[j]<a[i]&&l[j]>maxim) { k=j;maxim=l[k];}
        }
        if(k) { l[i]=l[k]+1; t[i]=k;}
            else { l[i]=1;t[i]=0;}
    }
    for(i=1;i<=n;i++)
    {
        if(l[i]>max) { max=l[i];g=i;}
    }
    fout<<max<<'\n';
    afish(g);
    return 0;
}

void afish(int k)
{
    if(k)
    {
        afish(t[k]);
        fout<<a[k]<<" ";
    }
}