Cod sursa(job #1770363)

Utilizator turnenTudor Oprescu turnen Data 4 octombrie 2016 09:45:36
Problema Subsir crescator maximal Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>

using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int v[100001];
int v1[100001];
int v2[100001];
int main()
{
    int n,i,j,mxp,mxdp=0;
    v1[1]=1;
    in>>n;
    for(i=1; i<=n; i++)
    {
        in>>v[i];
    }
    for(i=2; i<=n; i++)
    {
        v1[i]=1;
        for(j=i-1; j>=1; j--)
        {
            if(v[j]<v[i]&&v1[j]+1>v1[i])
            {
                v1[i]=v1[j]+1;
                v2[i]=j;
            }
        }
        if(v1[i]>mxdp)
        {
            mxdp=v1[i];
            mxp=i;
        }
    }
    out<<v1[mxp]<<'\n';
    i=mxp;
    while(v2[mxp]!=mxp){
    out<<v[mxp]<<' ';
    mxp=v2[mxp];
    }
}