Cod sursa(job #1581757)

Utilizator narcischitescuNarcis Chitescu narcischitescu Data 27 ianuarie 2016 09:28:27
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int n , a[100001], i , j , imax , amax;
int pred[100001] , v[100001] ;

void preluc ( int i )
{
    if ( pred[i] + 1 ) preluc( pred[i] );
    g << a[i] << " " ;
}

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

    pred[1] = -1;
    v[1] = 1;

    for ( i = 2; i <= n ; i++ )
    {
        pred[i] = -1;
        v[i] = 1;
        for ( j = 1 ; j < i; j++ )
        {
            if ( a[j] < a[i] and v[j] + 1 > v[i]  )
            {
                v[i] = v[j] + 1;
                pred[i] = j;
            }
        }
          if ( amax < v[i] ) amax = v[i] , imax = i;
    }
    g << v[imax] << "\n";
    preluc(imax);

    return 0;
}