Pagini recente » Cod sursa (job #700232) | Cod sursa (job #1802398) | Cod sursa (job #1584176) | Cod sursa (job #1911097) | Cod sursa (job #1726874)
#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>
using namespace std;
int main()
{
int N;
vector<int> a(100000);
vector<int> parent(100000);
vector<int> lungime(100000);
ifstream in("scmax.in");
ofstream out("scmax.out");
in >> N;
for(int i = 0; i < N; i++){
in >> a[i];
}
parent[N - 1] = N - 1;
lungime[N - 1] = N - 1;
for(int i = N - 1; i >= 0; i--){
int max_index = i;
for(int j = i + 1; j < N; j++){
if(a[i] < a[j] && lungime[max_index] < lungime[j]){
max_index = j;
}
}
lungime[i] = lungime[max_index] + 1;
parent[i] = max_index;
}
int maxx = 0;
for(int i = 1; i < N; i++){
if(lungime[i] > lungime[maxx]){
maxx = i;
}
}
int lungime_sol = 0;
while(maxx != parent[maxx]){
lungime[lungime_sol++] = a[maxx];
maxx = parent[maxx];
}
lungime[lungime_sol++] = a[maxx];
out << lungime_sol << '\n';
for(int i = 0; i < lungime_sol; i++){
out << lungime[i] << ' ';
}
return 0;
}