Cod sursa(job #485380)

Utilizator alinabBlaj Alina alinab Data 18 septembrie 2010 11:02:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
//Subsir crescator maximal infoarena
#include <fstream>

using namespace std;

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

int a[10000], n, l[10000], p[10000];

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

int maxim(int i)
{
    int max=0;
    for(int j=i+1;j<n;j++)
       if(a[i]<a[j] && l[j]>l[max])
         max=j;
    return max;
}

void creare()
{
    l[n-1]=1;
    p[n-1]=-1;
    for(int i=n-2;i>=0;i--)
    {
        int max=maxim(i);
        if(max==0)
        {
            l[i]=1;
            p[i]=-1;
        }
        else
        {
           l[i]=1+l[max];
           p[i]=max;
        }
    }
}

int maxim1()
{
    int max=0;
    for(int j=0;j<n;j++)
       if(l[max]<l[j])
         max=j;
    return max;
}

void afisare()
{
    int max=maxim1();
    fout<<l[max]<<endl;
    int i;
    for(i=max;p[i]!=-1;)
    {
        fout<<a[i]<<" ";
        i=p[i];
    }
    fout<<a[i];
}

int main()
{
    citire();
    creare();
    afisare();
    return 0;
}