Cod sursa(job #1281488)

Utilizator valentin11cCraciun Valentin-Gabriel valentin11c Data 3 decembrie 2014 11:15:08
Problema Subsir crescator maximal Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[100005],n,best[100005],maxx,pre[100005],sol[100005];

void citire()
{
    f>>n;
    for(int i=1;i<=n;i++) f>>a[i];

}
void afisare(int x)
{
    g<<maxx<<"\n";
    while(x>1)
    {
    sol[++sol[0]]=a[x];x=pre[x];
    }

    sort(sol+1,sol+sol[0]+1);
    for(int i=1;i<=sol[0];i++) g<<sol[i]<<" ";

}
void solve()
{
    for(int i=1;i<=n;i++)
    {

    for(int j=1;j<i;j++)
    {
        if(best[j]>best[i] && a[i]>a[j]) {best[i]=best[j];pre[i]=j;}
    }
    best[i]++;
    maxx=max(maxx,best[i]);

    }
    for(int i=1;i<=n;i++)
    {
        if(best[i]==maxx)
        {
            afisare(i);
        }
    }
}

int main()
{
    citire();
    solve();


    return 0;
}