Cod sursa(job #2090315)

Utilizator MarinPeptenaruMarin Vasile Peptenaru MarinPeptenaru Data 17 decembrie 2017 21:18:20
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
const int nx=100002;
int v[nx];
int n,pozmax,mx=INT_MIN;
int lg[nx],urm[nx];
int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
        in>>v[i];
    lg[n]=1;
    urm[n]=0;
    for(int i=n-1; i; i--)
    {
        lg[i]=1;
        urm[i]=0;
        for(int j=i+1; j<=n; j++)
        {
            if(lg[i]<lg[j]+1 && v[i]<v[j])
            {
                lg[i]=lg[j]+1;
                urm[i]=j;
            }
        }
        if(lg[i]>mx)
        {
            mx=lg[i];
            pozmax=i;
        }
    }
    out<<mx<<'\n';
    int p=pozmax;
    while(p)
    {
        out<<v[p]<<' ';
        p=urm[p];
    }
    return 0;
}