Cod sursa(job #1376644)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 5 martie 2015 18:10:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<fstream>
#include<iostream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int N,i,j,max1,pozu,dimrez;
int v[100001],rez[100001],p[100001];

int main()
{
    f>>N;
    for (i=1;i<=N;++i)
        f>>v[i];
    max1=1;
    for (i=1;i<=N;++i)
    {
        rez[i]=1;
        for (j=1;j<i;++j)
            if (v[i]>v[j] && rez[i]<rez[j]+1)
            {
                rez[i]=rez[j]+1;
                p[i]=j;
                if (rez[i]>max1)
                    max1=rez[i],pozu=i;
            }
    }
    g<<max1<<'\n';
    i=pozu;
    rez[++dimrez]=v[i];
    while (p[i]!=0)
    {
        i=p[i];
        rez[++dimrez]=v[i];
    }
    for (;dimrez>0;--dimrez)
        g<<rez[dimrez]<<' ';
    f.close();g.close();
    return 0;
}