Pagini recente » Cod sursa (job #2959538) | Cod sursa (job #784861) | Cod sursa (job #2253357) | Cod sursa (job #1259381) | Cod sursa (job #1244440)
#include <fstream>
using namespace std;
int l[100001];
int a[100001];
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int main()
{
int n;
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> a[i];
}
l[n] = 1;
int lmax = 1;
for (int i = n - 1; i >= 1; i--)
{
int max = 0;
for (int j = i + 1; j <= n; j++)
{
if (a[j] > a[i] && l[j] > max)
max = l[j];
}
l[i] = max + 1;
if (l[i] > lmax)
{
lmax = l[i];
}
}
fout << lmax << '\n';
/*determinarea drumului in O(n)*/
int p = 1;
while (l[p] != lmax)
p++;
fout << a[p] << ' ';
int aux = p;
lmax--;
while (lmax)
{
p++;
if (l[p] == lmax && a[aux] < a[p])
{
lmax--;
aux = p;
fout << a[p] << ' ';
}
}
}