Cod sursa(job #1665081)

Utilizator RazvanatorHilea Razvan Razvanator Data 26 martie 2016 16:08:01
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>

using namespace std;

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

int v[100001],lung[100001],pred[100001];
int n;

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

void sir(int p)
{
    if (pred[p]!=0)
        sir(pred[p]);
    fout<<v[p]<<' ';
}

int main()
{
    Read();
    int pmax=1;
    lung[1]=1;
    pred[1]=0;
    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;
    }
    fout<<lung[pmax]<<'\n';
    sir(pmax);
}