Pagini recente » tema | Cod sursa (job #1800197) | Cod sursa (job #2162405) | Cod sursa (job #3135190) | Cod sursa (job #2133581)
#include <fstream>
#define NMAX 100000
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[NMAX];
int lgmax[NMAX];
int urm[NMAX];
int n;
int main()
{
int i, j, maxim, urmator, pozmax;
fin>>n;
for(i=0; i < n; i++)
fin>>a[i];
//cel mai mic sufix are un element
lgmax[n-1] = 1;
urm[n-1] = -1;
for(i=n-2; i >= 0; i--)
{
maxim = 1;
urmator = -1;
for(j=i+1; j < n; j++)
if(a[i] < a[j] && 1 + lgmax[j] > maxim)
{
maxim = 1 + lgmax[j];
urmator = j;
}
lgmax[i] = maxim;
urm[i] = urmator;
}
//afisare
maxim = lgmax[0];
pozmax = 0;
for(i=1; i < n; i++)
if(lgmax[i] > maxim)
{
maxim = lgmax[i];
pozmax = i;
}
fout<<maxim<<endl;
fout<<a[pozmax]<<" ";
while(urm[pozmax] != -1)
{
pozmax = urm[pozmax];
fout<<a[pozmax]<<" ";
}
fout.close();
return 0;
}