Cod sursa(job #1596184)

Utilizator caprariuapCaprariu Alin-Paul caprariuap Data 10 februarie 2016 20:45:16
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int best[100003],a[100003],maxi,sol=0,poz[100003],p;
int n;
int i,j;
int main()
{
    f>>n;
    for (i=1; i<=n; i++) f>>a[i];
    best[1]=1;
    poz[1]=0;
    for (i=1; i<=n; i++)
    {
        int maxim=0,pozitie=0;
        for (j=1; j<i; j++)
            if (a[j]>maxim&&a[j]<a[i]) maxim=best[j],pozitie=j;
        best[i]=1+maxim;
        poz[i]=pozitie;
        if (best[i]>maxi) maxi=best[i],p=i;
    }
    g<<maxi<<'\n';
    i=p;j=1;
    while (i!=0)
    {best[j++]=a[i];
    i=poz[i];
    }
    for (i=j-1;i;i--)
        g<<best[i]<<' ';
    g<<'\n';
    return 0;
}