Cod sursa(job #1609410)

Utilizator FeriCsiki Francisc Alexandru Feri Data 22 februarie 2016 19:51:14
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int nr[100001],pre[100001],v[100001];
void subsir(int p)
{
    if(pre[p]!=0)
        subsir(pre[p]);
        out<<v[p]<<" ";
}
int main()
{
    int n,i,j,maxim=-1,pred=0;
    in>>n;
    for(i=1;i<=n;i++)
    {
        in>>v[i];
    }
    nr[1]=1;
    pre[1]=0;
    int pm=1;
    for(i=1;i<=n;i++)
    {
        nr[i]=0;
        pre[i]=0;
        for(j=1;j<i;j++)
        {
            if(v[j]<v[i])
                if(nr[j]>nr[i]){
                    nr[i]=nr[j];
                    pre[i]=j;
                    }
        }
        nr[i]++;
        if(nr[i]>nr[pm])
            pm=i;
    }
    for(i=1;i<=n;i++)
    {
        //out<<pre[i]<<" ";
        if(maxim<nr[i])
        {
            maxim=nr[i];
            pred=i;
        }
    }
    out<<maxim<<'\n';
    subsir(pm);
    return 0;
}