Cod sursa(job #1739775)

Utilizator maria15Maria Dinca maria15 Data 10 august 2016 10:39:02
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>

using namespace std;

int n, v[100003], L[100002], maxim, pozsol, w[100002], pmaxim, T[100002];

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


void drum(int p) {
    if (p!=0) {
        drum(T[p]);
        fout<<v[p]<<" ";
    }
}

int main () {

    fin>>n;
    for (int i=1;i<=n;i++)
        fin>>v[i];

    L[1] = 1;
    int sol = 1;
    for (int i=2;i<=n;i++) {
        maxim = 0;
        pmaxim = 0;
        for (int j=1;j<i;j++)
            if (v[j] < v[i] && L[j] > maxim) {
                maxim = L[j];
                pmaxim = j;
            }
        L[i] = 1 + maxim;
        T[i] = pmaxim;
        if (L[i] > sol) {
            sol = L[i];
            pozsol = i;
        }

    }
    fout<<sol<<"\n";
    drum(pozsol);
    /*
    int k=0;

    for(int i=pozsol;i!=0;i=T[i]){
        w[++k] = v[i];
    }

    for(int i=k;i>0;i--)
        fout<<w[i]<<" ";
    */
    return 0;
}