Cod sursa(job #1916765)

Utilizator georgeSigoiu7Sigoiu George georgeSigoiu7 Data 9 martie 2017 10:19:03
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,numere[100001],i,j,lungime[100001],predecesor[100001],lungimeMx,primulElement,pozitieCurenta;
int main()
{
    fin>>n;
    for(i=1; i<=n; i++)fin>>numere[i];

    lungime[n]=1;
    predecesor[n]=0;

    if(numere[n-1]<numere[n])
    {
        lungime[n-1]=2;
        predecesor[n-1]=n;
    }
    else
    {
        lungime[n-1]=1;
        predecesor[n-1]=0;
    }

    for(i=n-2; i>=1; i--)
    {
        lungime[i]=1;
        predecesor[i]=0;

        j=i+1;
        while(j<=n)
        {
            if(numere[i]<numere[j])
                lungimeMx=max(lungimeMx,lungime[j]);
            j++;
        }

        j=i+1;
        while(j<=n)
        {
            if(numere[i]<numere[j])
                if(lungime[j]==lungimeMx)
                {
                    lungime[i]=lungime[j]+1;
                    predecesor[i]=j;
                }
            j++;
        }
        lungimeMx=0;
    }
    for(i=1;i<=n;i++)
        if(lungimeMx<lungime[i])
    {
        primulElement=i;
        lungimeMx=lungime[i];
    }
    fout<<lungimeMx<<"\n";
    fout<<numere[primulElement]<<" ";
    pozitieCurenta=primulElement;
    while(predecesor[pozitieCurenta]!=0)
    {
        fout<<numere[predecesor[pozitieCurenta]]<<" ";
        pozitieCurenta=predecesor[pozitieCurenta];
    }
    return 0;
}