Cod sursa(job #2648359)

Utilizator rARES_4Popa Rares rARES_4 Data 10 septembrie 2020 13:10:57
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <iostream>
#include <stack>
using namespace std ;
ifstream f ("scmax.in") ;
ofstream g ("scmax.out");
stack<int> rasp;

int n,mx_rasp,v[100002],cresc[100002];
void afisare(int nr,int poz)
{
    if(nr == 0)
        return;
    for(int i = poz;;i--)
    {
        if(cresc[i] == nr)
        {
            afisare(nr-1,i-1);
            g << v[i]<< " ";
            return;
        }
    }
}
int main()
{
    f >> n;
    for(int i = 1; i<=n; i++)
    {
        f >> v[i];
    }
    for(int i = 1; i<=n; i++)
    {

        int mx = 0;
        for(int j = 1; j<i; j++)
        {
            if(v[j]<v[i])
                mx = max(mx,cresc[j]);
        }
        cresc[i] = mx+1;
    }
    for(int i = 1; i<=n; i++)
    {
        mx_rasp = max(mx_rasp,cresc[i]);
    }
    g << mx_rasp<< endl;
    afisare(mx_rasp,n);
    return 0 ;
}