Cod sursa(job #2441783)

Utilizator red_devil99Mancunian Red red_devil99 Data 21 iulie 2019 02:42:33
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define mx 100003

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

void sir(int n, int v[]){
    long long best[mx];
    long long poz[mx];
    best[1] = 1;
    poz[1] = 0;
    int b = 1;
    for(int i = 2; i <= n; i++){
    	best[i] = 1;
    	for(int j = 1; j < i ; j++){
    		if(v[i] > v[j] && (best[i] < best[j] + 1)){
    			   best[i] = best[j] + 1;
    			   poz[i] = j;
    			     
                
            }
    		
    	}
    }

    int sol = best[1];
    int pos = 1;
    for(int i = 2; i <= n; i++){
    	if(best[i] > sol){
    		sol = best[i];
    		pos = i;
    	}
    }
    

   fout << sol <<'\n';
   int vec[mx];
   for(int i = 1; i<= sol; i++){
   	vec[sol-i+1] = v[pos];
    pos = poz[pos]; 
   }

   for(int i = 1; i<= sol; i++){
      fout << vec[i] << " ";
   }
  

}

int main(){
	int n;
	int v[mx];
	fin >> n;
	for(int i = 1; i <=n; i++){
		fin >> v[i];
	}
	sir(n, v);
	return 0;
}