Pagini recente » Cod sursa (job #899531) | Cod sursa (job #2231738) | Cod sursa (job #2362728) | Cod sursa (job #831576) | Cod sursa (job #2907091)
#include<stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
//https://infoarena.ro/problema/scmax
int main()
{
std::vector<int> arr;
std::vector<int> len;
std::vector<int> prev;
std::ifstream fin("scmax.in");
std::ofstream fout("scmax.out");
int n, len_max, ind_max, ind;
fin >> n;
arr.resize(n);
len.resize(n);
prev.resize(n);
for (int i = 0; i < n; i++)
fin >> arr[i];
for (int i = n - 1; i >= 0; i--)
{
len[i] = 1;
len_max = 0;
ind = -1;
for (int j = i + 1; j < n; j++)
{
if (arr[i] < arr[j] && len[j] > len_max)
{
len_max = len[j];
ind = j;
}
}
if (ind != -1)
len[i] += len[ind];
prev[i] = ind;
}
len_max = 0;
ind_max;
for (int i = 0; i < n; i++)
{
if (len[i] > len_max)
{
len_max = len[i];
ind_max = i;
}
}
fout << len_max << '\n';
while (ind_max != -1)
{
fout << arr[ind_max] << ' ';
ind_max = prev[ind_max];
}
}