Cod sursa(job #2263023)

Utilizator VinaAndreeaVina Andreea VinaAndreea Data 18 octombrie 2018 00:13:56
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 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,maxi=0,pozmax=0,lg,pozitie;
    sol[n]=1;
    for(i=n-1;i>=1;i--)
    {
        lg=0;
        for(j=i+1;j<=n;j++)
        {
            if(v[i]<v[j] && sol[j]+1>lg)
                lg=sol[j]+1,pozitie=j;
        }
        if(lg==0)
            sol[i]=1,urm[i]=0;
        else sol[i]=lg,urm[i]=pozitie;
    }
    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]);
    }
}