Pagini recente » Cod sursa (job #1041788) | Cod sursa (job #217214) | Cod sursa (job #2590228) | Cod sursa (job #2265382) | Cod sursa (job #2628190)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int h[100001], e[100001], n, i, j, maxi;
long int a[100001], ans[100001];
int main()
{
fin >> n;
for (i = 0; i < n; i++)
{
fin >> a[i];
e[i] = -1;
}
h[0] = 1;
for (i = 1; i < n; i++)
{
maxi = i;
for (j = i-1; j >= 0; j--)
{
if (a[j] < a[i] && h[j] > h[maxi])
maxi = e[i] = j;
}
if (e[i] != -1)
h[i] = h[maxi]+1;
else
h[i] = 1;
}
int max_h = 0;
for (i = 1; i < n; i++)
{
if (h[i] > h[max_h])
max_h = i;
}
for (i = h[max_h]-1, j = max_h; i >= 0; i--)
{
ans[i] = a[j];
j = e[j];
}
fout << h[max_h] << "\n";
for (i = 0; i < h[max_h]; i++)
fout << ans[i] << " ";
/*
for (i = 0; i < n; i++)
fout << a[i] << " ";
fout << "\n";
for (i = 0; i < n; i++)
fout << h[i] << " ";
fout << "\n";
for (i = 0; i < n; i++)
fout << e[i] << " ";
*/
}
// n 11
// a 24 12 15 9 20 19 6 32 21 23 16
// i 0 1 2 3 4 5 6 7 8 9 10
// h 1 1 2 1 3 3 1 4 4 5 3
// e -1 -1 1 -1 2 2 -1 5 5 8 2
/* pseudo solution
main()
{
for 1 to n
{
for i-1 to 0
{
//find number with the highest length which is at the same time smaller than a[i]
if found a number
{
maxi = j;
e[i] = maxi;
}
}
if (e[i] != -1)
h[i] = h[maxi]+1;
}
find the max val of h[]
print the wanted elements
}
*/