Cod sursa(job #2543653)

Utilizator ionut.birisBiris Ionut ionut.biris Data 11 februarie 2020 13:21:47
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 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];
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]){
                rez[i] = rez[j]  +1;
                urm[i] = j;
            }
    }
}

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

    }

    return 0;
}