Pagini recente » Cod sursa (job #1405277) | Cod sursa (job #2716952) | Cod sursa (job #918293) | Cod sursa (job #3229880) | Cod sursa (job #3210409)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
const int NMAX = 100001;
int v[NMAX];
int lmax[NMAX];
int n,lm,pozmax,next_i;
int nexti[NMAX];
int scmax(int k){
if(lmax[k] != -1)
{
return lmax[k];
}
int best_lmax = 1;
for(int i = k + 1; i <= n; i++)
{
if(v[i] > v[k])
{
int lmax_from_i = scmax(i);
if(lmax_from_i + 1 > best_lmax)
{
best_lmax = lmax_from_i + 1;
if(lmax[i]>lm)
{
lm=lmax[i];
next_i=i;
}
}
}
}
nexti[k]=next_i;
lmax[k] = best_lmax;
return lmax[k];
}
int main()
{
f >> n;
for(int i = 1; i <= n; i++){
f >> v[i];
lmax[i] = -1;
}
int best = 1;
for(int i = 1; i <= n; i++){
int lmax_for_i = scmax(i);
if(lmax_for_i > best){
best = lmax_for_i;
pozmax=i;
}
}
g << best << "\n";
int cur=pozmax;
while(cur!=0)
{
g << v[cur] << " ";
cur=nexti[cur];
}
return 0;
}