Cod sursa(job #1117200)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 23 februarie 2014 11:41:36
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <fstream>
using namespace std;
long nr[100001],max1[100001],next[100001],gmax,sf;
 
int main ()
{
	long i,j,N,crt;
	ifstream f("scmax.in");
    /*freopen("scmax.in", "r", stdin);
    
    scanf("%d", &N);
    for (i=1; i<=N; i++)
    {
        scanf("%d", &nr[i]);
    }*/
	f>>N;
	for (i=1; i<=N; i++) f>>nr[i];
    for (i=N; i>=1; i--)
    {
        max1[i]=1;
        gmax=0;
        for (j=N; j>=i+1; j--)
            if (nr[i]<nr[j] && max1[j]>max1[gmax]) gmax=j;
        if (gmax) max1[i]=max1[gmax]+1;
        if (max1[i]>max1[sf]) sf=i;
        next[i]=gmax;
    }
	
	freopen("scmax.out", "w", stdout);
    printf("%d\n", max1[sf]);
    crt=nr[sf];
    for (i=sf; next[i]; i=next[i]) printf("%d ", nr[i]);
    printf("%d", nr[i]);
	
    //printf("\n");
    //for (i=1; i<=N; i++) printf("%d ", next[i]);
    return 0;
}