Cod sursa(job #1739774)

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

using namespace std;

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

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

    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";
    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;
}