Cod sursa(job #1570091)

Utilizator nicholascantarNicholas David Cantar Gogitidze nicholascantar Data 16 ianuarie 2016 10:49:22
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>

using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int a[100001],l[100001],n,mx,k;
void solve()
{
    int i,j;
    l[n]=1;
    for (i=n-1;i>=1;i--)
    {
        mx=0;
        for (j=i+1;j<=n;j++)
            if (l[j]>mx&&a[i]<a[j]) mx=l[j];
        l[i]=mx+1;
    }
    mx=0;
    for (i=1;i<=n;i++)
        if (l[i]>mx)
    {
        mx=l[i];
        k=i;
    }
}
void afis()
{
    int i;
    fout<<mx<<'\n';
    for (i=k;i<=n&&mx;i++)
        if(l[i]==mx)
    {
        fout<<a[i]<<" ";
        mx--;
    }
}
int main()
{
    int i;
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>a[i];
    solve();
    afis();
    return 0;
}