Cod sursa(job #1739797)

Utilizator castle2145Popa Catalin castle2145 Data 10 august 2016 11:38:13
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#define NMAX 100001

using namespace std;

int a[NMAX];
int n;
int B[NMAX];
int s[NMAX];
int l;
int P[NMAX];

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

int calculB ()
{
    B[1]=1;
    P[1]=0;

    int i, j, max, maxl;

    for(i=2; i<=n; i++)
    {
        max=0;
        P[i]=0;

        for(j=1; j<=i-1; j++)
            if(a[j]<a[i] && max<B[j])
            {
                max=B[j];
                P[i]=j;
            }

        B[i]=max+1;
    }

    max=0;
    for(i=1;i<=n;i++)
        if(B[i]>max)
            max=B[i], maxl=i;

    return maxl;
}

void construire ()
{
    int m, i, k;

    //calculez indicele celui mai lung subsir
    m=1;
    for(i=2; i<=n; i++)
        if(B[i]>B[m])
            m=i;
    k=B[m];

    l=k;

    s[k]=a[m];
    while(P[m]>0)
    {
        m=P[m];
        k--;
        s[k]=a[m];
    }
}

void afisare (int l)
{
    int i;
    fout<<l-1<<'\n';
    for(i=1;i<=l-1;i++)
        fout<<s[i]<<' ';

}

int main()
{
    fin>>n;
    int i;
    for(i=1; i<=n; i++)
        fin>>a[i];

    int lung=calculB();

    construire();
    afisare(lung-1);

    return 0;
}