Cod sursa(job #1998265)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 7 iulie 2017 09:20:06
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int v[200001];
int secv[200001], poz[200001];
int m, n, plec;

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

void rezolvare(){
  for(int i = n; i >= 1; i--){
    secv[i] = 1;
    for(int j = i + 1; j <= n; j++){
      if(secv[j] + 1 > secv[i] && v[i] < v[j]){
        secv[i] = secv[j] + 1;
        poz[i] = j;
        break ;
      }
    }
    if(m < secv[i]){
        m = secv[i];
        plec = i;
    }
  }
  out << m << '\n';
  for(int i = plec ; i != 0; i = poz[i]){//pana nu termin de sarit pasii : poz[i]
    out << v[i] << ' ';
  }
}


int main(){
  citire();
  rezolvare();
  return 0;
}