Cod sursa(job #1863076)

Utilizator rangrazvanRang Razvan Victor rangrazvan Data 30 ianuarie 2017 17:32:21
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#define MAX 100001
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int lung[MAX],pred[MAX],n,v[MAX];

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

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

    for (int i=2;i<=n;i++)
    {
        if (lung[i]>lung[pmax])
        {
            pmax=i;
        }
    }

    g<<lung[pmax]<<endl;
    sir(pmax);
    return 0;
}