Cod sursa(job #677234)

Utilizator informatician28Andrei Dinu informatician28 Data 9 februarie 2012 22:25:08
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<fstream> 
#define DIM 100001
using namespace std; 

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

int V[DIM], Best[DIM], Apar[DIM], indice, maxim;
int N;

void print(int pos)
{
	if( Apar[pos] == 0 )
	{
		out << V[pos]<< " "; 
		return;
	}
	else
	{
		print(Apar[pos]);
		out << V[pos] << " ";
	}
	
}
	
int main()
{
	int i, k, position;
	
	in >> N;
	for(i = 1; i <= N; i++)
		in >> V[i];
	
	for(i = 1; i <= N; i++)
		{
			maxim = 0;
			for(k = i-1; k >=1; k--)
		    {
			    if( V[i] > V[k] )
				    if( maxim < Best[k] ) 
					    {
							maxim = Best[k];
							indice = k;
					}
		    }
			if( maxim  )
				{
					Best[i] = maxim + 1;
					Apar[i] = indice;
			}
			else 
			{
				Best[i] = 1;
				Apar[i] = 0;
			}
	}
	
	maxim = 0;
	for(i = 1; i <= N; i++)
		if( Best[i] > maxim )
			{
				maxim = Best[i];
                position = i;
            }
		
		out << maxim << '\n';
		print(position);
}