Cod sursa(job #2544192)

Utilizator ionut.birisBiris Ionut ionut.biris Data 11 februarie 2020 20:37:21
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
const int NMAX = 100005;

int a[NMAX],N;
int rez[NMAX],urm[NMAX];
int start;
int subsir[NMAX];
int maxim = -100;
void read(){
    f >> N;
    for(int i = 1; i<= N;i++)
        f >> a[i];
}

void scmax(){
    rez[N] = 1;
    urm[N] = -1;
    for(int i = N-1; i >=1;i--){
        rez[i] = 1;
        urm[i] = -1;
        for(int j = i + 1; j <= N;j++)
            if(a[i] < a[j] && rez[i] < rez[j] + 1 ){
                rez[i] = rez[j]  +1;
                urm[i] = j;
                if(rez[i] > maxim){
                    start = i;
                    maxim = rez[i];
                }
            }
    }
}

int main()
{
    read();
    scmax();
    g << maxim<<"\n";
    g << a[start] << " ";
    for(int i = 1; i < maxim;i++){
        start = urm[start];
        g << a[start] << " ";

    }

    return 0;
}