Pagini recente » Cod sursa (job #1136317) | Cod sursa (job #832903) | Cod sursa (job #2609419) | Borderou de evaluare (job #1848894) | Cod sursa (job #3242403)
//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, t;
int last;
void drum(int u)
{
if (u != -1)
{
drum(t[u]);
fout << v[u] << ' ';
}
}
int main()
{
int n, maxim = 0, p_maxim = 0, p;
fin >> n;
v.resize(n);
t.resize(n, -1);
dp.resize(n, 1);
for (int i = 0; i < n; ++i)
fin >> v[i];
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; ++j)
if (v[j] < v[i] && dp[j] + 1 > dp[i])
{
dp[i] = dp[j] + 1;
p = j;
}
if (dp[i] != 1)
t[i] = p;
else
t[i] = -1;
if (dp[i] > maxim)
{
maxim = dp[i];
p_maxim = i;
}
}
fout << maxim << '\n';
last = v[p_maxim];
drum(p_maxim);
}