Cod sursa(job #1713105)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 4 iunie 2016 18:24:29
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <algorithm>
#define MAX 2000000
#define INF 2000000005
using namespace std;
 
char f[MAX];
int pos=0,size[100005]={0,1},bef[100005]={},N,v[100005]={},out[100005];
void r(int &nr)
{
    nr=0;
    while(f[pos]<'0'||f[pos]>'9')
        pos++;
    while(f[pos]>='0'&&f[pos]<='9')
        nr=nr*10+f[pos++]-'0';
}

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
 
    fread(f,1,MAX,stdin);

	r(N);
	for(int i=1;i<=N;i++)
		r(v[i]);
	v[N+1]=INF;
	for(int i=2;i<=N+1;i++)
	{
		int Max=0,mpos=0;
		for(int j=1;j<i;j++)
			if(v[i]>v[j]&&Max<size[j])
			{
				Max=size[j];
				mpos=j;
			}
		size[i]=Max+1;
		bef[i]=mpos;
	}
	int i=N+1;
	printf("%d\n",size[N]);
	while(bef[i]>0)
	{
		out[++out[0]]=v[bef[i]];
		i=bef[i];
	}
	for(int i=out[0];i>0;i--)
		printf("%d ",out[i]);
    return 0;
}