Pagini recente » Cod sursa (job #883416) | Cod sursa (job #2307386) | Cod sursa (job #2486620) | Cod sursa (job #573660) | Cod sursa (job #2541653)
#include <iostream>
#include <fstream>
#define NMAX 100000
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int n,a[NMAX],poz[NMAX],best[NMAX],p,maxim;
void citire()
{
in>>n;
for(int i=1;i<=n;i++)
in>>a[i];
}
void dinamic()
{
best[n] = 1;
poz[n] = -1;
maxim = 1;
p = n;
for(int i=n-1;i>=1;i--)
{
best[i] = 1;
poz[i] = -1;
for(int j=i+1;j<=n;j++)
if(a[i] < a[j] && best[i] < best[j] + 1)
{
best[i] = best[j] + 1;
poz[i] = j;
if(maxim < best[i])
{
maxim = best[i];
p = i;
}
}
}
}
void afisare()
{
int i = p;
out<<maxim<<'\n';
while(i != -1)
{
out<<a[i]<<" ";
i = poz[i];
}
}
int main()
{
citire();
dinamic();
afisare();
}