Cod sursa(job #1609407)

Utilizator teodoramusatoiuTeodora Musatoiu teodoramusatoiu Data 22 februarie 2016 19:50:23
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int lung[100005],pred[100005],n;
long long a[100005];

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

int main()
{
    int i,j,max=0,p;
    in>>n;
    for(i=1; i<=n; i++)
        in>>a[i];
    lung[1]=1;
    for(i=2; i<=n; i++)
    {
        lung[i]=0;
        pred[i]=0;
        for(j=1; j<i; j++)
            if(a[j]<a[i])
                if(lung[j]>lung[i])
                {
                    lung[i]=lung[j];
                    pred[i]=j;
                }
        lung[i]++;
        if(lung[i]>max)
        {
            max=lung[i];
            p=i;
        }
    }
    out<<max<<'\n';
    afis(p);
    return 0;
}