Cod sursa(job #2407087)

Utilizator marius0072scarlat marius stefan marius0072 Data 16 aprilie 2019 14:34:10
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 100000;
int n,v[NMAX + 5],lis[NMAX + 5],maxx,posmax;

void Print(int index,int maxx){
    if(maxx > 0 && index >= 0 && lis[index] == maxx){
        Print(index - 1, maxx - 1);
        g << v[index] << " ";
    }else if(index >= 0 && maxx > 0)
        Print(index - 1,maxx);
}

int main(){
    f >> n;
    for(int i = 0;i < n;i++)
        f >> v[i];
    // Largest increasing subsequence
    lis[0] = 1;
    maxx = posmax = 0;
    for (int i = 1; i < n; i++ )
    {
        lis[i] = 1;
        for (int j = 0; j < i; j++ )
            if ( v[i] > v[j] && lis[i] < lis[j] + 1)
                lis[i] = lis[j] + 1;
        if(lis[i] > maxx){
            maxx = lis[i];
            posmax = i;
        }
    }
    
    g << maxx << "\n";
    
    Print(posmax, maxx);
  
}