Cod sursa(job #544298)

Utilizator feelshiftFeelshift feelshift Data 1 martie 2011 13:12:22
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
// http://infoarena.ro/problema/scmaxim
#include <fstream>
#include <cstring>
using namespace std;

#define maxSize 100001

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

int length,maxim,lastPosition;
int number[maxSize];
int best[maxSize];
int previous[maxSize];

void reconstruct(int position);

int main() {
    in >> length;
    for(int i=1;i<=length;i++) {
        in >> number[i];
        best[i] = 1;
        previous[i] = i;
    }

    for(int i=2;i<=length;i++)

        for(int k=1;k<i;k++)
            if(number[k] < number[i] && best[i] < best[k] + 1) {
                best[i] = best[k] + 1;
                previous[i] = k;

                if(best[i] > maxim) {
                    maxim = best[i];
                    lastPosition = i;
                }
            }

    out << maxim << "\n";

    reconstruct(lastPosition);

    in.close();
    out.close();

    return (0);
}

void reconstruct(int position) {
    // daca nu e "radacina" (pointeaza
    // spre el insusi)
    if(previous[position] != position)
        reconstruct(previous[position]);
    out << number[position] << " ";
}