Cod sursa(job #1789840)

Utilizator SenibelanMales Sebastian Senibelan Data 27 octombrie 2016 15:57:21
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#define MAX_LENGTH 100007

using namespace std;

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

int v[MAX_LENGTH], dp[MAX_LENGTH], succ[MAX_LENGTH], n;

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

void Solve(){
  for(int i = n; i >= 1; --i){
    int max = 0;
    for(int j = i + 1; j <= n; ++j){
      if(v[i] < v[j] && dp[j] > max){
	max = dp[j];
	succ[i] = j;
      }
    }
    dp[i] = max + 1;
  }
}

void Print(){
  int max = 0, p;
  for(int i = 1; i <= n; ++i){
    if(dp[i] < max){
      max = dp[i];
      p = i;
    }
  }
  out << max << "\n";
  while(p){
    out << v[p] << " ";
    p = succ[p];
  }
  out << "\n";
}

int main(){
  Read();
  Solve();
  Print();
  return 0;
}