maxdevm.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION

Dada una secuencia de numeros (a_1,a_2,...,a_n), vamos a
decir que su "maxima desviacion", es la maxima
diferencia (en valor absoluto) entre todos sus numeros: 
maxdev(a_1,a_2,...,a_n) = max_(j=1,n) a_j - min_(j=1,n) a_j
Escribir una funcion "function MAX\_DEV\_M(L:lista; m:integer) :
integer;" que retorna el maximo de las maximas desviaciones de las
subsecuencias de L de longitud m. 
Por ejemplo, si (1,3,5,4,3,5), entonces MAX\_DEV\_N(L,3)
debe retornar 4 ya que la maxima desviacion se da en la primera
subsecuencia (1,3,5) y es 4. Se sugiere el siguiente algoritmo,
para cada posicion p en la lista hallar la maxima
desviacion de los m elementos siguientes (incluyendo a 
p). Hallar la maxima de estas desviaciones. Keywords: lista

  FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id: separa.pas 2002/04/05 18:15 jdelia  Exp jdelia      $}

program maxdevm_p;

uses u_listpi;

type
  lista	= listpi ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function  MAX_DEV_M(L : lista; m:integer): integer;
var
   p,q	 : posicion;
   val_p,val_q,retval,c : integer;
begin

   p := L.primero;
   retval := 0;
   while p<>L.fin do
   begin
      val_p := L.recupera(p);
      q:=L.siguiente(p);
      c:=2;
      while (q<>L.fin) and (c<=m) do
      begin
	 val_q := L.recupera(q);
	 if (val_q-val_p)>retval then retval := val_q-val_p;
	 q:=L.siguiente(q);
	 c:= c+1;
      end;
      p:=L.siguiente(p);
   end;
   MAX_DEV_M := retval;
end; { MAX_DEV_M }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
   L	   : Lista;
   j,val,m,N : integer;
begin	
   L.anula;
   N := 3;

   L.inserta(1,L.fin);
   L.inserta(3,L.fin);
   L.inserta(5,L.fin);
   L.inserta(4,L.fin);
   L.inserta(3,L.fin);
   L.inserta(5,L.fin);
   
   { genera una lista creciente aleatoria }
{    randomize;}
{    val := 0;}
{    for j:=1 to 20 do}
{    begin}
{       val := val + random(2*N+1) - N;}
{       L.inserta(val,L.fin);}
{    end;}
   L.imprime ('L:');

   writeln('MAX_DEV_M: ', MAX_DEV_M(L,3));
   
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}