Cod sursa(job #1181627)

Utilizator tudormaximTudor Maxim tudormaxim Data 3 mai 2014 13:26:18
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#define inf 200000000
#define NMAX 100005
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int main()
{
    int n,x[NMAX],i,j,lis[NMAX];
    in>>n;
    for(i=1;i<=n;i++)
        in>>x[i];
    lis[n]=1;
    for(i=1;i<n;i++)
        lis[i]=0;
    for(i=n;i>0;i--)
    {
        int max=0;
        for(j=i+1;j<=n;j++)
        {
            if(max<lis[j]&&x[j]>x[i])
                max=lis[j];
        }
        lis[i]=max+1;
    }
    int max=lis[1];
    for(i=1;i<=n;i++)
    {
        if(lis[i]>max)
            max=lis[i];
    }
    out<<max<<"\n";
    int poz=1,k,min,p;
    for(k=max;k>0;k--)
    {
        min=inf;
        for(i=poz;i<=n;i++)
        {
            if(x[i]<min&&lis[i]==k)
            {
                p=i;
                min=x[i];
            }
        }
        poz=p;
        out<<x[p]<<" ";
    }
    in.close();
    out.close();
}