Cod sursa(job #1046114)

Utilizator cadirmDirman Catalin cadirm Data 2 decembrie 2013 18:05:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int x[100000],n,pred[100000],lung[100000];

void sir(int p)
{
    if(pred[p]!=0)
        sir(pred[p]);
    out<<x[p]<<" ";
}

void citire()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>x[i];
}

void dinamic()
{
    lung[1]=1;
    for(int i=2;i<=n;i++)
    {
        int max1=0;
        for(int j=1;j<=i-1;j++)
            if(x[i]>x[j] && lung[j]>max1)
            {
                max1=lung[j];
                pred[i] = j;
            }
        lung[i]=max1+1;
    }
}

void afisare()
{
    int a=0,c=0;
    for(int i=1;i<=n;i++)
        if(lung[i]>a)
        {
            a=lung[i];
            c=i;
        }
    out<<a;
    out<<endl;
    sir(c);
}
int main()
{
    citire();
    dinamic();
    afisare();
    return 0;
}