Cod sursa(job #1358286)

Utilizator alexandru94hahahalera alexandru94 Data 24 februarie 2015 15:21:23
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>

using namespace std;



void show(int a[], int prev[], int i)
{
	if(i){
		show(a, prev, prev[i]);
		cout<<a[i]<<" ";
	}
	
}

int main()
{
	int N;
	int a[100001];
	int best[100001];
	int prev[100001];
	int i, j;
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	
	cin >> N;
	for(i = 1; i <= N; i++)
	{
		cin >> a[i];
	}
	best[1] = 1;
	prev[1] = 0;
	
	for(i = 1; i <= N; i++)
	{
		int maxi = 0;
		int maxipoz = 1;
		for(j = 1; j < i; j++)
		{
			if(a[j] < a[i] && maxi < best[j])
			{
				maxi = best[j];
				maxipoz = j;
			} 
			
		}
		best[i] = 1 + maxi;
		prev[i] = maxipoz;
	}
	
	int l = 0, pos = 0;
	for(i = 1; i <= N; i++)
	{
		if(l < best[i]) {
			l = best[i];
			pos = i;
		}
	}
	
	cout<<l<<"\n";
	i = pos;
	
	
	//cout<<"prev[1] = "<<prev[1]<<"\n";
	prev[1] = 0;
	
	show(a, prev, i);
	/*
	while(i) 
	{
		cout<<a[i]<<" ";
		i = prev[i];
	}
	*/
	return 0;
}