Cod sursa(job #2576723)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 6 martie 2020 22:04:11
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

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

const int NMAX = 100005;

vector<int>q;
int poz[NMAX],v[NMAX];
vector<int>sol;
int n;

int main()
{
	fin >> n;
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		fin >> v[i];
		if (q.empty())
		{
			q.push_back(v[i]);
			poz[i] = 0;
			cnt = max(cnt, poz[i]);
			continue;
		}
		vector<int>::iterator it = lower_bound(q.begin(), q.end(), v[i]);
		if (it == q.end())
		{
			q.push_back(v[i]);
			poz[i] = q.size() - 1;
			cnt = max(cnt, poz[i]);
			continue;
		}
		*it = v[i];
		poz[i] = it - q.begin();
		cnt = max(cnt, poz[i]);
	}
	for (int i = n; i >= 1; i--)
	{
		if (poz[i] == cnt)
		{
			sol.push_back(v[i]);
			cnt--;
		}
	}
	fout << sol.size() << "\n";
	for (int i = sol.size() - 1; i >= 0; i--)
		fout << sol[i] << " ";
	return 0;
}