Cod sursa(job #1666306)

Utilizator sebastiannrxRichiteanu Mihai Sebastian sebastiannrx Data 27 martie 2016 21:15:52
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,i,j,k,ma,v[100001],t[100001],l[100001];
int main()
{   f>>n;
    for (i=1;i<=n;++i)
        f>>v[i];
    l[n]=1;
    t[n]=0;
    for (i=n-1;i>=1;--i) {
        ma=0;
        for (j=i+1;j<=n;++j)
            if (v[j]>v[i] && l[j]>ma) {
                ma=l[j];
                k=j;}
        t[i]=k;
        l[i]=ma+1;}
    ma=0;
    for (i=1;i<=n;++i)
        if (ma<l[i]) {
            ma=l[i];
            k=i;}
    g<<ma<<'\n';
    while (ma>0) {
        g<<v[k]<<" ";
        k=t[k];
        --ma;

    }
    return 0;
}