Cod sursa(job #853905)

Utilizator ilenitudorIleni Tudor ilenitudor Data 12 ianuarie 2013 15:43:14
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n,maxx,pmax;
long int a[100005],l[100005];

void Read()
{
    fin>>n;
    for(int i=1 ; i<=n ; i++)
    fin>>a[i];
}

void fl()
{
    l[n]=1;
    for(int i=n-1 ; i>=1 ; i--)
    {
        for(int k=i+1; k <=n ; k++)
        if(a[i] < a[k] && l[i]<=l[k] )
        l[i]+=1+l[k];
    }

}
void afis()
{
    fout<<a[pmax]<<" ";
    int t=pmax;
    for(int i=pmax+1 ; i<=n ; i++ )
    {
        if(l[i]+1 == l[t] && a[i]>a[t])
        {
            fout<<a[i]<<" ";
            t=i;
        }
    }
}
int main()
{
    Read();
    fl();
    for(int i=1 ; i<=n ; i++)
    {
        if(maxx < l[i])
        {
            maxx = l[i];
            pmax = i;
        }
    }
    fout<<maxx<<endl;
    afis();

    fin.close();
    fout.close();
    return 0;
}