Cod sursa(job #2263019)

Utilizator VinaAndreeaVina Andreea VinaAndreea Data 18 octombrie 2018 00:05:32
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,v[100005],sol[100005],urm[100005];
void citire();
void rezolvare();
void afisare(int poz);
int main()
{
    citire();
    rezolvare();
    return 0;
}
void citire()
{
    int i;
    fin >> n;
    for(i=1;i<=n;i++)
        fin >> v[i];
}
void rezolvare()
{
    int i,j,k,maxi=0,pozmax=0;
    sol[n]=1;
    k=n-1;
    for(i=k;i>=1;i--)
    {
        for(j=i+1;j<=n;j++)
        {
            if(v[j]>v[i] && sol[j]+1>sol[i])
                sol[i]=sol[j]+1,urm[i]=j;
        }
    }
    for(i=1;i<=n;i++)
        if(sol[i]>maxi)
            maxi=sol[i],pozmax=i;
    fout << maxi << '\n';
    afisare(pozmax);
}
void afisare(int poz)
{
    if(poz==0)
        return;
    else
    {
        fout << v[poz] << ' ';
        afisare(urm[poz]);
    }
}