Cod sursa(job #1173920)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 21 aprilie 2014 10:54:20
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
using namespace std;

ifstream is("scmax.in");
ofstream os("scmax.out");

int n, a[100001];
int c[100001], t[100001];
int maxim, imax;

void WRITE(int x);

int main()
{
    is >> n;
    for ( int i = 1; i <= n; ++i )
    {
        is >> a[i];
        c[i] = 1;
        for ( int j = 1; j < i; ++j )
            if ( a[j] < a[i] && c[j] + 1 > c[i] )
                c[i] = c[j] + 1, t[i] = j;
        if ( c[i] > maxim )
            maxim = c[i], imax = i;
    }
    os << maxim << "\n";
    WRITE(imax);
    is.close();
    os.close();
    return 0;
}

void WRITE(int x)
{
    if ( !x )
        return;
    WRITE(t[x]);
    os << a[x] << " ";
}