Cod sursa(job #1043464)

Utilizator cypry97Dascalitei Ciprian cypry97 Data 28 noiembrie 2013 17:18:53
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int n;
long long v[101];
int lis[101];

/*void solutie(int s, int p, int k, int sol[])
{
    if(p==0)
    {
        for(int i=1;i<=k-1;i++)
            out<<sol[i]<<' ';
        out<<'\n';
        return ;
    }
    for(int i=s;i<=n;i++)
        if(lis[i]==p&&v[i]>sol[k-1])
        {
            sol[k]=v[i];
            solutie(i+1,p-1,k+1,sol);
        }
}*/

int main()
{
    int i,j,maxx;
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    lis[n]=1;
    for(i=n-1;i;i--)
    {
        maxx=0;
        for(j=i+1;j<=n;j++)
            if(v[i]<v[j]&&maxx<lis[j])
                maxx=lis[j];
        lis[i]=maxx+1;
    }
    /*
    maxx=0;
    for(i=1;i<=n;i++)
    {
        if(lis[i]>=maxx)
        {
            if(lis[i]>maxx)
                {
                    maxx=lis[i];
                    p=i;
                }
            else if(v[i]<v[p])
                p=i;
        }
    }
    cout<<v[p]<<' ';
    u=v[p];
    for(i=maxx-1;i;i--)
    {
        maxx--;
        for(j=p+1;lis[i]!=maxx&&v[j]<u;j++);
        p=j;
        for(j++;j<=n;j++)
            if(lis[j]==maxx)
                if(v[i]<v[p]&&v[i]>u)
                    p=j;
        cout<<v[p]<<' ';
        u=v[p];
    }
    */
    /*maxx=0;
    for(i=1;i<=n;i++)
        if(lis[i]>maxx)
            maxx=lis[i];
    int sol[101];
    for(i=1;i<=n;i++)
        if(lis[i]==maxx)
        {
            sol[1]=v[i];
            solutie(i+1,maxx-1,2,sol);
        }*/
    maxx=0;
    for(i=1;i<=n;i++)
        if(maxx<lis[i])
            maxx=lis[i];
    out<<maxx<<'\n';
    out.flush();
    int u;
    v[0]=-300000;
    u=0;
    while(maxx)
    {
        for(i=u+1;i<=n;i++)
            if(lis[i]==maxx&&v[i]>v[u])
            {
                out<<v[i]<<' ';
                u=i;
                i=n+1;
            }
        maxx--;
    }
    return 0;
}