Cod sursa(job #285053)

Utilizator titusuTitus C titusu Data 22 martie 2009 12:31:35
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
/*
 * 
 * Determina subsirul crescator maximal folosid algoritmul clasic, de complexitate n*n
 * 
 * */
#include <stdio.h>
#define DIM 100001
typedef int Vector[DIM];
FILE *fin=fopen("scmax.in","r");
FILE *fout=fopen("scmax.out","w");

Vector v, p, l;
int n;

void SCM()
{
  int i,j;
  l[n]=1, p[n]=-1;
  for(i=n-1;i;i--)
  {
    l[i]=1, p[i]=-1;
    for(j=1;j<=n;j++)
      if(v[i]<v[j] && l[i]<l[j]+1)
        l[i]=l[j]+1, p[i]=j;
  }
}

void Afisare()
{
  int pmax=1;
  for(int i=1;i<=n;i++)
    if(l[i]>l[pmax])
      pmax=i;
  fprintf(fout,"%d\n",l[pmax]);
  while(pmax!=-1)
    fprintf(fout,"%d ",v[pmax]), pmax=p[pmax];
}

void Citire()
{
  fscanf(fin,"%d",&n);
  for(int i=1;i<=n;i++)
    fscanf(fin,"%d",v+i);
}

int main()
{
  Citire();
  SCM();
  Afisare();
  return 0;
}