Cod sursa(job #2541653)

Utilizator Galatanu_BogdanGalatanu Bogdan Ioan Galatanu_Bogdan Data 8 februarie 2020 17:57:52
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#define NMAX 100000
using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");

int n,a[NMAX],poz[NMAX],best[NMAX],p,maxim;

void citire()
{
    in>>n;
    
    for(int i=1;i<=n;i++)
        in>>a[i];
}

void dinamic()
{
    best[n] = 1;
    poz[n] = -1;
    maxim = 1;
    p = n;
    for(int i=n-1;i>=1;i--)
    {
        best[i] = 1;
        poz[i] = -1;
        
        for(int j=i+1;j<=n;j++)
            if(a[i] < a[j] && best[i] < best[j] + 1)
            {
                best[i] = best[j] + 1;
                poz[i] = j;
                
                if(maxim < best[i])
                {
                    maxim = best[i];
                    p = i;
                }
            }
    }
}

void afisare()
{
    int i = p;
    out<<maxim<<'\n';
    while(i != -1)
    {
        out<<a[i]<<" ";
        i = poz[i];
    }
}

int main()
{
    citire();
    dinamic();
    afisare();
}