Pagini recente » Cod sursa (job #635640) | nationala-care-a-spart-globul-pamantesc | Cod sursa (job #2385194) | Cod sursa (job #2716921) | Cod sursa (job #3242402)
//https://www.infoarena.ro/problema/scmax
#include <fstream>
#include <vector>
std::ifstream fin("scmax.in");
std::ofstream fout("scmax.out");
using namespace std;
int max(int a, int b)
{
return a > b ? a : b;
}
vector<int> v, dp;
int last;
void show(int i, int cnt_maxim)
{
if (cnt_maxim == 0 || i < 0)
return;
if (v[i] < last && dp[i] == cnt_maxim)
{
last = v[i];
show(i - 1, cnt_maxim - 1);
fout << v[i] << ' ';
}
else
show(i - 1, cnt_maxim);
}
int main()
{
int n, maxim = 0, p_maxim = 0;
fin >> n;
v.resize(n);
dp.resize(n, 1);
for (int i = 0; i < n; ++i)
fin >> v[i];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < i; ++j)
if (v[j] < v[i])
dp[i] = max(dp[i], dp[j] + 1);
if (dp[i] > maxim)
{
maxim = dp[i];
p_maxim = i;
}
}
fout << maxim << '\n';
last = v[p_maxim];
show(p_maxim - 1, maxim - 1);
fout << v[p_maxim];
}