Cod sursa(job #1426765)

Utilizator gallexdAlex Gabor gallexd Data 30 aprilie 2015 16:54:37
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
#include <vector>
#include <iostream>

using namespace std;

int N, maxim, length;
int V[100100], bst[100100];
vector<int> Q;
int poz;
int main () {

  cin >> N;
  for (int i=0; i<N; ++i)
    cin >> V[i];
  
  for (int i=0; i<N; ++i) {
    maxim = 0;
    for (int j=0; j<i; ++j)
      if (V[j] < V[i] && bst[j] > maxim)
	maxim = bst[j];
    bst[i] = maxim + 1;
    if (bst[i] > length) {
      length = bst[i];
      poz = i;
    }
  }
  cout << length << "\n";
  int i = poz;
  Q.push_back(V[poz]);
  --length;
  while (length) {
    if (bst[i] == length && V[i] < V[poz]) {
      Q.push_back(V[i]);
      length--;
      poz = i;
    }
    --i;
  }

  for (int i=Q.size()-1; i>=0; --i) {
    cout << Q[i] << " ";
  }

  return 0;
}