Cod sursa(job #1665096)

Utilizator savigunFeleaga Dragos-George savigun Data 26 martie 2016 16:14:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
using namespace std;

int v[100001], lung[100001], pred[100001];
ifstream in("scmax.in");
ofstream out("scmax.out");
void sir(int p)
{
    if(pred[p]!=0)
        sir(pred[p]);
    out<<v[p]<<" ";
}

int main()
{
int n, pmax, i, j;

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

lung[1] = 1;
pred[1] = 0;
pmax = 1;

for(int i = 2; i <= n; i++) {
    lung[i] = 0;
    for(int j = 1; j < i; j++)
        if(v[j] < v[i])
            if(lung[j] > lung[i])
            {
                lung[i] = lung[j];
                pred[i] = j;
            }
    lung[i]++;
    if(lung[i]>lung[pmax])
        pmax = i;
}

out<<lung[pmax]<<endl;
sir(pmax);

    return 0;
}