Cod sursa(job #904739)

Utilizator miu_mik93FMI - Paduraru Miruna miu_mik93 Data 4 martie 2013 20:12:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<iostream>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <iomanip>
#include <string>
using namespace std;
#define DIMMAX 100
int n;
long long int *l, *v;
void citire()
{
	FILE *f = fopen("scmax.in", "r");
	fscanf(f, "%d", &n);
	l = new long long int[n+1];
	v = new long long int[n+1];
	for (int i=1; i<=n; i++)
		fscanf(f, "%d", &v[i]);

	fclose(f);
}
int main()
{	
	int Max;
	
	citire();	
	
	l[n] = 1;
	for (int i = n-1; i >= 1; i--)
	{
		Max = 0;
		int k;
		for (k = i+1; k <= n; k++)
			if (v[k] > v[i] && l[k] > Max)
				Max = l[k];
		l[i] = Max + 1;
	}
	
	Max = l[1]; int poz = 1;
	for (int i=2; i<=n; i++)
		if(Max < l[i])
			Max = l[i], poz = i;
	
	FILE *g = fopen("scmax.out", "w");
	fprintf(g, "%d\n", Max);
	fprintf(g, "%d ", v[poz]);
	
	for (int i = poz + 1; i <= n; i++)
		if(v[i] > v[poz] && l[i] == Max-1)
			fprintf(g, "%d ", v[i]), Max--;
	
	fclose(g);
	
	return 0;
}