Pagini recente » Cod sursa (job #1661348) | Cod sursa (job #621041) | Cod sursa (job #147814) | Cod sursa (job #166415) | Cod sursa (job #2910164)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 100000
using namespace std;
vector<int> numbers;
int n = 0;
int best[NMAX], smax = 0, sol = 0, pos[NMAX], p;
void algo()
{
best[n] = 1;
pos[n] = -1;
smax = 1;
p = n;
for(auto i = n - 1; i >= 1; --i)
{
best[i] = 1;
pos[i] = -1;
for(auto j = i + 1; j <= n; ++j)
{
if(numbers[i] < numbers[j] && best[i] < best[j] + 1)
{
best[i] = best[j] + 1;
pos[i] = j;
if(best[i] > smax)
{
smax = best[i];
p = i;
}
}
}
}
}
int main()
{
ifstream fin("scmax.in");
ofstream fout("scmax.out");
auto aux = 0;
fin >> n;
for(auto i = 0; i < n; i++)
{
fin >> aux;
numbers.push_back(aux);
}
algo();
int k = p;
fout << smax << '\n';
while(k != -1)
{
fout << numbers[k] << " ";
k = pos[k];
}
fin.close();
fout.close();
return 0;
}