Cod sursa(job #1860985)

Utilizator theodor1289Theodor Amariucai theodor1289 Data 28 ianuarie 2017 15:12:19
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int v[100010], lung[100010], pred[100010], i, indicemax, mx;
int n;

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

int main()
{
    std::ios::sync_with_stdio(false);
    fin>>n;
    fin>>v[1];i=1;
    lung[1]=1;

    for(int k=1;k<n;k++)
    {
        fin>>v[++i];
        mx=0;
        for(int j=1;j<i;j++)
            {
                if(v[j]<v[i])
                {
                    if(lung[j]>mx)
                        mx=lung[j], pred[i]=j;
                }
            }
        lung[i]=mx+1;
        if(lung[i]>lung[indicemax])
            indicemax=i;
    }
    fout<<mx+1<<'\n';
    subsir(indicemax);

    return 0;
}