Cod sursa(job #1922905)

Utilizator SirbuSirbu Ioan Sirbu Data 10 martie 2017 19:32:29
Problema Subsir crescator maximal Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

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

int v[100002];
int best[1002];
int afis[1002];


void afisare (int i){

  if (i > 0){
    afisare(afis[i]);
    fout << v[i] << " ";
  }

}

int main (){

  int n;
  fin >> n;
  for (int i = 1; i <= n; ++i)
    fin >> v[i];

  best[1] = 1;
  int best_max = 0;
  int poz_max = 0;
  for (int i = 2; i <= n; ++i){
    int max_ind = 0;
    for (int j = i-1; j >= 1; j--){
      if (best[j] > best[max_ind] && v[i] > v[j])
        max_ind = j;
    }
    afis[i] = max_ind;
    best[i] = best[max_ind] + 1;

    if (best[i] > best_max){
      best_max = best[i];
      poz_max = i;
    }
  }

  fout << best_max << "\n";
  afisare(poz_max);


}