Cod sursa(job #2526470)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 18 ianuarie 2020 18:00:00
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
//ALEXANDRU MICLEA

#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

//#include <iostream>
#include <fstream>
ifstream cin ("scmax.in"); ofstream cout ("scmax.out")

//VARIABLES
int n;
int v[100005];
int best[100005];
int last[100005];
int MAX = 1;
int pos = n;

//FUNCTIONS

//MAIN
int main() {

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

	best[n] = 1;
	last[n] = -1;

	for (int i = n-1; i >= 1; i--) {
		best[i] = 1;
		last[i] = -1;
		for (int j = i+1; j <= n; j++) {
			if (v[i] < v[j] && best[i] < best[j] + 1) {
				best[i] = best[j] + 1;
				last[i] = j;
				if (best[i] > MAX) {
					MAX = best[i];
					pos = i;
				}
			}
		}
	}

	cout << MAX << '\n';

	int i;
	i = pos;
	while (i != -1) {

		cout << v[i] << " ";
		i = last[i];
	}

	return 0;
}