Cod sursa(job #1164224)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 1 aprilie 2014 22:38:22
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
using namespace std;
int x[100];
int m[100];
int ne[100];
int main()
{
	ifstream f("scmax.in");
	ofstream g("scmax.out");
	int n,i,j,smax=-1,poz,d=0;
	f>>n;
	for (i=1;i<=n;i++)
	{
	    f>>x[i];
	    if (x[i-1]==x[i]) d++;
	}
	for (i=n;i>=1;i--)
	{
		m[i]=1;
		ne[i]=-1;
		for (j=i+1;j<=n;j++)
			if (x[i] <= x[j]&& m[i]<=m[j]) {m[i]=m[j]+1;ne[i]=j;}
	}
	for (i=1;i<=n;i++)
        if (smax<m[i]) {smax=m[i];poz=i;}
	g<<smax-d<<'\n'<<x[poz]<<" ";
	for (i=2;i<=smax;i++)
        if (x[poz]!=x[ne[poz]]) {poz=ne[poz];g<<x[poz]<<" ";}
        else poz++;
	g<<'\n';
	f.close();
	g.close();
	return 0;

}