Cod sursa(job #2183092)

Utilizator serjiuuAvacaritei Sergiu serjiuu Data 22 martie 2018 20:13:08
Problema Subsir crescator maximal Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>

using namespace std;

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

const int nmax=100005;
int n, maxi, p;
int a[nmax], poz[nmax], l[nmax];

void read()
{
    int i;

    fin>>n;

    for(i=1;i<=n;i++)
        fin>>a[i];
}

void solve()
{
    int i, j;

    for(i=n;i>=1;i--)
    {
        l[i]=1;
        poz[i]=-1;

        for(j=i+1;j<=n;j++)
            if(a[j]>a[i] && l[i]<l[j]+1)
            {
                l[i]=l[j]+1;
                poz[i]=j;
            }
        if(l[i]>maxi)
        {
            maxi=l[i];
            p=i;
        }
    }
}

void print()
{
    int i;

    fout<<maxi<<'\n';

    for(i=1;i<=n;i++)
        fout<<poz[i]<<' ';
    fout<<endl;

    i=p;

    while(i!=-1)
    {
        fout<<a[i]<<' ';
        i=poz[i];
    }
}

int main()
{
    read();
    solve();
    print();
}