Cod sursa(job #1836475)

Utilizator alexandruchiriacAlexandru Chiriac alexandruchiriac Data 28 decembrie 2016 13:42:26
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;

#define nrmax 100001

ifstream f("scmax.in");
ofstream g("scmax.out");

int n;
int a[nrmax],v[nrmax],pre[nrmax];

void drum ( int i )
{
    if ( pre[i] ) drum(pre[i]);
    if ( i >= 1 and i <= n ) g << v[i] << " " ;
}

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

    memset(pre,-1,sizeof pre);

    for ( int i = 2; i <= n ; i++ )
    {
        a[i] = 1;
        for ( int j = 1; j < i; j++ )
        {
            if ( v[j] < v[i] and a[j] + 1 > a[i] )
            {
                a[i] = a[j]+1;
                pre[i] = j;
            }
        }
    }
    int amax = 1, poz = 2;
    for ( int i = 1 ; i <= n ; i++ )
        if ( amax < a[i] ) amax = a[i] , poz = i;
    g << amax << "\n" ;
    drum(poz);
    return 0;
}