Cod sursa(job #1037537)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 20 noiembrie 2013 12:50:24
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<iostream>
#include<fstream>
#include<cstdio>
using namespace std;

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

int n,a[100005],dp[100005],next[100005],mm,poz,poz1,next1[100005],nnex;

inline void Citire()
{
    fin>>n;
    for (int i=1;i<=n;i++)
        fin>>a[i];
}

inline void Formeaza()
{
    int i,j,nr,maxim;
    for (i=1;i<=n;i++)
        {
            nr=0;maxim=-1;
            for (j=i-1;j>=1;j--)
                if (a[j]<a[i])
                        if (dp[j]>maxim)
                            {maxim=dp[j];poz1=j;}
            if (maxim!=-1) {dp[i]=maxim+1;next[i]=poz1;}
            else {dp[i]=1;next[i]=0;}
            if (dp[i]>mm) {mm=dp[i];poz=i;}
        }
    fout<<mm<<"\n";
    i=poz;
    while (next[i]!=0)
        {
            next1[++nnex]=a[i];
            i=next[i];
        }
    next1[++nnex]=a[i];
    for (int i=nnex;i>=1;i--)
        fout<<next1[i]<<" ";
    fout<<"\n";
}

int main()
{
    Citire();
    Formeaza();
    return 0;
}