Cod sursa(job #701717)

Utilizator soriynSorin Rita soriyn Data 1 martie 2012 17:28:15
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
#include<algorithm>
#define maxn 100010

using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int a[maxn];
int l[maxn];
int n,maxim,poz;
void read()
{
	in>>n;
	for(int i=1;i<=n;i++)
		in>>a[i];
}

void solve()
{
	l[n]=1;
	maxim=1;
	poz=n;
	for(int i=n-1;i>=1;i--)
	{
		int maxi=0;
		for(int j=i+1;j<=n;j++)
		{
			
			if(a[i]<a[j]) 
			  { 
				  if(l[j]>maxi) maxi=l[j];
			  }
		}
		l[i]=maxi+1;
		if(l[i]>maxim) maxim=l[i],poz=i;
	}
}

int main()
{
	read();
	solve();
	out<<maxim<<"\n";
	out<<a[poz]<<" ";
	maxim--;
    for(int i=poz;i<=n && maxim>0;i++)
	{
		if(a[i]>a[poz] && l[i]==maxim)
		{
			poz=i;
			out<<a[i]<<" ";
			maxim--;
		}
	}
}