Cod sursa(job #1358918)

Utilizator ClaudiuHHiticas Claudiu ClaudiuH Data 24 februarie 2015 20:37:04
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>

using namespace std;

long n,lung[100000],urm[100000],a[100000],maxim=0;
int i,j,indice;

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

int main()
{
    fin>>n;
    for(i = 1 ; i <= n ; ++ i)
        fin>>a[i];
    for(i = n ; i >= 1 ; -- i)
        lung [i] = 1;
    for(j = n ; j > 1 ; -- j)
    {
        if(a[i] < a[j])
            if(lung[1] < lung[j] + 1)
        {
            lung[i] = lung[j] + 1;
            urm[i] = j;
            if(lung[i] > maxim)
            {
                maxim = lung[i];
                indice = i;

            }
        }
    }

    fout<<maxim<<'\n';
    while(indice != 0)
    {
        cout<<a[indice]<<" ";
        indice = urm[indice];
    }

    return 0;
}