Cod sursa(job #1088817)

Utilizator mihaitapaulMihaita Paul mihaitapaul Data 20 ianuarie 2014 20:52:47
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <cstring>
using namespace std;
#define DMAX 100001
FILE*fin=fopen("scmax.in","r");
ofstream fout("scmax.out");
int n,lgmax,pozmax,solutie[DMAX];
struct punct
{
    int val;
    int lg;
    int pred;
};
punct sir[DMAX];
void citire()
{
    fscanf(fin,"%d",&n);
    for(int i=1; i<=n; i++)
    {
        fscanf(fin,"%d",&sir[i].val);
        sir[i].lg=0;
        sir[i].pred=0;
    }
}
void pd()
{
	int i,j;
    sir[1].lg=1;
    for(int i=2; i<=n; i++)
    {
        sir[i].lg=1;
        sir[i].pred=0;
        for(int j=1; j<i; j++)
        {
            if(sir[j].val<sir[i].val&&sir[j].lg+1>sir[i].lg)
            {
                sir[i].lg=sir[j].lg+1;
                sir[i].pred=j;
            }
        }
    }
}
void sol()
{
    int i,j;
    lgmax=0;
    for(i=1; i<=n; i++)
        if(lgmax<sir[i].lg)
        {
            lgmax=sir[i].lg;
            pozmax=i;
        }
    i=pozmax;
    int ind=0;
    while(i!=0)
    {
        solutie[++ind]=sir[i].val;
        i=sir[i].pred;
    }
}
void afisare()
{
	fout<<lgmax<<'\n';
	for(int i=lgmax;i>0;i--)
		fout<<solutie[i]<<' ';
}
void nr_de_subsiruridelgmax()
{

}
int main()
{
    citire();
    pd();
    sol();
    afisare();
    nr_de_subsiruridelgmax();
    return 0;
}