Cod sursa(job #1232869)

Utilizator 0051David Sera 0051 Data 24 septembrie 2014 09:09:23
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int a[100002],b[100002],z[100002];

int main()
{
    int n,i,j;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    for(i=1;i<=n;i++)
    {
        for(j=1;j<i;j++){
            if(a[i]>a[j])
                b[i]=max(b[i],b[j]);
        }
        b[i]++;
    }
    int m=0,h=0;
    for(i=1;i<=n;i++){
        m=max(m,b[i]);
        if(b[i]==m)
            j=i;
    }
    fout<<m<<endl;
    z[++h]=a[j];
    m--;
    for(i=j;i>0;i--)
    {
        if(b[i]==m && a[i]<a[j]){
            z[++h]=a[i];
            m--;
            j=i;
        }
    }
    for(i=h;i>0;i--)
        fout<<z[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}