Pagini recente » Monitorul de evaluare | Rating Antonio Nitoi (4N70N1U5) | Istoria paginii runda/pregatire2021_3/clasament | Cod sursa (job #1609744) | Cod sursa (job #2321809)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
void afis(int v[100001], int tata[200000], int index)
{
if (tata[index] == -1)
return;
afis(v, tata, tata[index]);
out << v[index] << " ";
}
int main()
{
int n, v[100001];
in >> n;
for (int i = 0; i < n; i++)
in >> v[i];
int dp[100001], tata[200000], iFinal = 0;
tata[0] = -1;
dp[0] = 1;
for (int i = 1; i < n; i++)
{
int lMax = -1;
for (int j = 0; j < i; j++)
{
if (v[j] < v[i] && dp[j] > lMax)
{
lMax = dp[j];
tata[i] = j;
iFinal = i;
}
}
dp[i] = lMax == -1 ? dp[i - 1] : max(dp[i - 1], 1 + lMax);
}
out << dp[n - 1] << endl;
afis(v, tata, iFinal);
return 0;
}