Cod sursa(job #609916)

Utilizator ichigo2908mantu radu ichigo2908 Data 23 august 2011 20:31:09
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
using namespace std;
typedef struct lis
{
	int v, l, p;
};

int ok=0;
lis sir[100000];

ofstream g("scmax.out");

int main()
{
	int start, max=0, n, i, j;
	ifstream f("scmax.in");
	f>>n;
	for(i=0;i<n;i++)
	{
		f>>sir[i].v;
		sir[i].l=1;
		sir[i].p=-1;
		for(j=0;j<i;j++)
			if((sir[j].l>=sir[i].l)&&(sir[j].v<sir[i].v))
			{
				sir[i].l=sir[j].l+1;
				sir[i].p=j;
			}
		if(sir[i].l>max)
		{
			max=sir[i].l;
			start=i;
		}
	}
	f.close();
	int x[100000], o=0;
	while(ok!=2)
	{
		x[o]=sir[start].v;
		o++;
		start=sir[start].p;
		if(sir[start].p==-1)
			ok++;
		if(start==0)
			ok=2;
	}
	g<<o<<"\n";
	for(i=o-1;i>=0;i--)
		g<<x[i]<<" ";
	g.close();
	return 0;
}