Cod sursa(job #1309140)

Utilizator killlerr1Chilom Mircea killlerr1 Data 5 ianuarie 2015 13:29:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
using namespace std;

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

long long a[100001], b[100001], pos[100001], p, m;

int n;

void Read();


int main()
{
    Read();
    b[n] = 1;
    pos[n] = -1;

    for( int i = n-1; i >= 1; --i )
    {
        b[i] = 1;
        pos[i] = -1;

        for(int j = i+1; j <= n; ++j )
            if( a[i] < a[j] && b[i] < b[j]+1 )
            {
                b[i] = b[j]+1;
                pos[i] = j;
                    if(b[i] > m)
                    {
                        m = b[i];
                        p = i;
                    }
            }
    }


    os << m << '\n';

    int i = p;

    while( i != -1 )
    {
        os << a[i] << ' ';
        i = pos[i];
    }

    is.close();
    os.close();
    return 0;
}

void Read()
{
    is >> n;
    for( int i = 1; i <= n; ++i )
        is >> a[i];
}