Pagini recente » Cod sursa (job #1808958) | Cod sursa (job #2710893) | Cod sursa (job #2566978) | Cod sursa (job #895290) | Cod sursa (job #3210402)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
const int NMAX = 100005;
int n,v[NMAX],lm[NMAX];
int next_elem[NMAX];
int scm(int m)
{
if(lm[m]!=-1)
{
return lm[m];
}
int best_lmax = 1;
next_elem[m] = -1;
for(int i=m;i<=n;i++)
{
if(v[i]>v[m])
{
int lmax_from_i = scm(i);
if (lmax_from_i + 1 > best_lmax) {
best_lmax = lmax_from_i + 1;
next_elem[m] = i;
}
}
}
lm[m] = best_lmax;
return lm[m];
}
int main()
{
int maxx = -1, elem_lmax = 0, index;
fin >> n;
for(int i=1;i<=n;i++)
{
fin >> v[i];
lm[i]=-1;
}
for (int i = 1; i <= n; i++) {
int lmax = scm(i);
if (lmax > maxx) {
maxx = lmax;
elem_lmax = i;
}
}
fout << maxx << "\n";
index = elem_lmax;
while(index != -1) {
fout << v[index] << " ";
index = next_elem[index];
}
return 0;
}