Cod sursa(job #953813)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 27 mai 2013 13:23:02
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int n,i,j,u,maxim,k;
int v[100010],f[100010],s[100010],t[100010];
int main (){

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];

    for (i=1;i<=n;i++) {
        maxim=0;u=0;
        for (j=1;j<i;j++)
            if (v[i]>v[j]&&f[j]>maxim){ maxim=f[j]; u=j;}
        f[i]=maxim+1;
        t[i]=u;
    }
    maxim=0;
    for (i=1;i<=n;i++)
        if (f[i]>maxim) {maxim=f[i]; u=i;}

    fout<<maxim<<"\n";
    while (u!=0) {
        s[++k] = v[u];
        u=t[u];
    }
    for (i=maxim;i>=1;i--)
        fout<<s[i]<<" ";

    return 0;
}