Pagini recente » Cod sursa (job #2750173) | Cod sursa (job #2236395) | Cod sursa (job #2025542) | Cod sursa (job #2753142) | Cod sursa (job #2135736)
#include <iostream>
#include <fstream>
#define NMAX 100001
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int a[NMAX], lgmax[NMAX], urm[NMAX], n;
void citire();
void afis();
int main()
{
int urmator;
int maxim;
int i;
int j;
citire();
//dinamica
//cel mai mic sufix are un element
lgmax[n-1]=1; urm[n-1]=-1;
for (i=n-2; i>=0; i--)
{
urmator=-1;
maxim=1;
for (j=i+1; j<n-maxim+1; j++)
if (a[i]<a[j] && 1+lgmax[j]>maxim)
{
maxim=1+lgmax[j];
urmator=j;
}
lgmax[i]=maxim; urm[i]=urmator;
}
//afisare
//cout<<"da";
afis();
return 0;
}
void afis ()
{
int i;
int maxim=1, poz=0;
for (i=0; i<n-maxim; i++)
if (lgmax[i]>maxim)
{
maxim=lgmax[i];
poz=i;
}
fout<<maxim<<'\n';
fout<<a[poz];
while (urm[poz]!=-1)
{
poz=urm[poz];
fout<<' '<<a[poz];
}
fout<<'\n';
fout.close();
}
void citire()
{
int i;
fin>>n;
for (i=0; i<n; i++)
fin>>a[i];
}