Cod sursa(job #1914991)

Utilizator tanasaradutanasaradu tanasaradu Data 8 martie 2017 19:16:01
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
///Varianta o(n^2)
int n,a[nmax],lis[nmax],sol[nmax],nsol;
void Citire()
{
    int i;
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>a[i];
}
void Rezolvare()
{
    int i,j,mx;
    lis[1]=1;
    for(i=2; i<=n; i++)
    {
        mx=0;
        for(j=i-1; j>=1; j--)
            if(a[j]<a[i] && mx<lis[j])
                mx=lis[j];
        lis[i]=1+mx;
    }
    mx=0;
    for(i=1; i<=n; i++)
        mx=max(mx,lis[i]);
    fout<<mx<<"\n";
    for(i=n; i>=1; i--)
        if(lis[i]==mx)
        {
            sol[++nsol]=a[i];
            mx--;
        }
    for(i=nsol; i>=1; i--)
        fout<<sol[i]<<" ";
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}