Cod sursa(job #433235)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 3 aprilie 2010 14:48:10
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<iostream>
#include<fstream>
#define MAX_N 100005

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int N, v[MAX_N], D[MAX_N], k, i, j, poz, maxim, mx;

int main()
{
	fin>>N;
	for(i=1;i<=N;i++)
		fin>>v[i];
	D[N] = 1;
	
	for(k=N-1;k>=1;k--)
	{
		int mx=0;
		for(j=k+1;j<=N;j++)
			if(v[j]>v[k] && D[j]>mx)
				mx = D[j];
		D[k] = mx + 1;
		if(D[k] > maxim)
		{
			maxim = D[k];
			poz = k;
		}
	}
	
	fout<<maxim<<"\n";
	fout<<v[poz]<<" ";
	for(i=poz+1;i<=N;i++)
		if(D[i] == maxim - 1)
		{
			fout<<v[i]<<" ";
			maxim--;
		}
	return 0;
}