Cod sursa(job #517742)

Utilizator DanceKrissCristian Oancea DanceKriss Data 29 decembrie 2010 18:08:29
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include<stdio.h>
using namespace std;

const long int lg=100000;

int v[lg],L[lg],N,p,m;



void read()
{
    cin>>N;

    for(int i=1; i<=N; i++)
     cin>>v[i];
}

void solve()
{
    int i,j,mx;
    L[N]=1;

    for(i=N-1;i>0;i--)
    {
       mx=0;

       for(j=i+1;j<=N;j++)
           if(v[j]>v[i] && L[j]>mx) mx=L[j];

       L[i]=mx+1;
       if(L[i]>m)  p=i,m=L[i];
    }
}

void out()
{
    cout<<m<<'\n';
    cout<<v[p];
    for(int i=p+1;i<=N;i++)
     if(L[i]==m-1 && v[p]<v[i]) {cout<<' '<<v[i];m--;}


}


int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    read();
    solve();
    out();
    return 0;
}