Pagini recente » Cod sursa (job #2137391) | Cod sursa (job #2134243)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
std::ifstream in("scmax.in");
std::ofstream out("scmax.out");
const int MAX_N =100000 +10;
int N;
int v[MAX_N]{0}, best[MAX_N]{0}, pind[MAX_N]{0};
int main()
{
in >> N;
for(int i =1 ; i <= N ; i++)
in>>v[i], best[i] = 1, pind[i]=i;
best[0] = 0;
int bi;
for(int i = 2 ; i <= N ; i++)
{
bi = 0;
for(int j = 1 ; j< i ; j++)
if(v[j]<v[i]&& best[j] > best[bi])
bi = j;
if(bi!=0)
{
best[i] = 1+best[bi];
pind[i] = bi;
}
}
int * el = max_element(best+1,best+1+N);
int poz = 1;
for(int i = 2 ; i <= N ; i++)
if(best[i]>best[poz])
poz = i;
for(int i = *el ; i >=1 ; i--)
{
best[i] = v[poz];
poz = pind[poz];
}
out<<*el<<'\n';
for(int i = 1 ; i<= *el ; i++)
out<<best[i]<<" ";
return 0;
}