Cod sursa(job #2648352)

Utilizator rARES_4Popa Rares rARES_4 Data 10 septembrie 2020 12:55:12
Problema Subsir crescator maximal Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 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];
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;
    for(int i = 1; i<=n; i++)
    {
        if(cresc[i] == mx_rasp)
        {
            rasp.push(v[i]);
            int predecesor = v[i];
            for(int j = i; j>=1; j--)
            {
                if(v[j]<predecesor)
                {
                    predecesor = v[j];
                    rasp.push(v[j]);
                }

            }
            while(!rasp.empty())
            {
                g << rasp.top()<< " ";
                rasp.pop();
            }
            return 0;
        }
    }
    return 0 ;
}