Buenos dias

Bueno, Antes de empezar tengo que decir que mi fuerte no es el analisis
algoritmico. Mas bien todo lo contrario. Trabajando en la programacion
orientada a sistemas las posibilidades de tener que enfrentarse a
problemas como el que Victor nos plantea son mas bien escasas. Esta es
desde luego uno de los grandes atractivos de este reto. Una buena
oportunidad para desenpolvar los viejos y escasos conocimientos sobre
analisis algoritmico. Sin mas, y esperando leer el resto de soluciones,
y por que no decirlo, esperando tambien aprender algo sobre estos temas
tan interesantes, comienzo la exposicion de mi solucion :oD

Comenzare fijando algunas variables que no estaban del todo definidas
en la especificacion del problema a solucionar. Dire que intentare que
mis soluciones encuentren ademas de la sublista con el sumatorio mayor,
la sublista mas larga. Para ello ante sublistas con el mismo sumatorio
siempre voy a elegir la ultima encontrada. Como se vera mas adelante,
esto garantiza que sea la mas larga, y ademas que coincidan los
resultados para los dos algoritmos que voy a proponer. Por contra,
esta especificacion hace el algoritmo mas lento, aunque no modifica su
complejidad.

Ademas de esto, Victor proponia la busqueda del algoritmo mas optimo, y
no cerraba la cuestion de adquisicion de los datos para la aplicacion
del algoritmo. En este sentido Yo voy a optar por medir su compleijdad,
dejando de lado cualquier optimizacion que vaya mas alla de la del propio
algoritmo. Mis soluciones seran funciones que reciban la lista de enteros
en una estructura que contenga un puntero a la lista junto con su tamaņo,
y que devuelvan el offset en el que comienza la solucion, tomando el
pimer elemento como offset cero, y el tamaņo de la lista.


PRIMERA SOLUCION. LA APROXIMACION GENERICA

A esta solucion la llamo la aproximacion generica porque es un metodo
de analisis que es aplicable a multitud de problemas de diversa indole.
Si pensamos para una posible entrada de tamaņo n, una matriz de nxn, en
la que cada elemento Mi,j representa el resultado del sumatorio de la
sublista que va desde el i-esitmo hasta el j-esimo elemento, nuestro
problema sera simplemente encontrar el elemento maximo en esa matriz.
Es evidente que esa matriz guarda todos los posibles sumatorios, y
ademas es tambien evidente que esa matriz es simetrica respecto de su
diagonal principal, por lo que solo necesitamos recorrer los elementos por
encima o por debajo de su diagonal. Ahora solo necesitamos pensar en como
construir esa matriz, y que informacion es realmente importante almacenar.

La informacion de la que disponemos inicialmente son los elementos de su
diagonal principal, Mi,i, y es facil definir una funcion que a partir de
esa diagonal construya los de la diagonal superior, Puesto que:

     Mi,i+1 = Mi,i + Mi+1,i+1

que podemos generalizar como

     Mi,i+t = Mi,i+t-1 + Mi+t,i+t

De esta manera estamos definiendo un sistema iterativo para ir construyendo
las sucesivas diagonales, hasta obtener el triangulo superior de la matriz.
Ademas, los datos obtenidos en las diagonales inferiores nos pueden servir
para obtener las nuevas diagonales, de forma que minimizamos el numero de
operaciones a realizar.

Por ultimo, si segun vamos calculando guardamos el elemento maximo
encontrado hasta el momento, podemos ir descartando las diagonales segun
las vamos calculando, puesto que para obtener las diagonales superiores,
solo necesitamos la inmediatamente inferior y la diagonal principal
inicial, de manera que solo necesitaremos un array de tamaņo n auxiliar
para realizar todos los calculos.

Este algoritmo calcula todos los sumatorios de todas las sublistas, por
lo que garantizamos que encontraremos siempre la solucion, salvo error en
la implementacion. El codigo seria el siguiente:

typedef struct _LIST_DATA
{
  DWORD dwSize;
  LPINT pData;
}LIST_DATA,*PLIST_DATA;


void
FindMaxSubList(PLIST_DATA lpListData, LPDWORD lpdwStartOffset, LPDWORD
lpdwSize)
{
  LPINT lpAuxList;

  lpAuxList = (LPINT) HeapAlloc(GetProcessHeap(),0,lpListData->dwSize * sizeof(INT));
  
  if(lpAuxList)
  {
    DWORD i;
    DWORD j;
    INT Max;

    RtlZeroMemory(lpAuxList, lpListData->dwSize * sizeof(INT));
    Max = lpListData->pData[0];
    for(i=0;i<lpListData->dwSize;i++)
    {
      for(j=0;j<lpListData->dwSize-i;j++)
      {
        lpAuxList[j] += lpListData->pData[j+i];
        if( lpAuxList[j] >= Max)
        {
          Max = lpAuxList[j];
          *lpdwStartOffset = j;
          *lpdwSize = i+1;
        }
      }
    }
    HeapFree(GetProcessHeap(),0,lpAuxList);
  }
}


De este algoritmo hay que notar que no admite una lista vacia como
entrada, puesto que inicializamos el maximo al primer elemento de la
lista para comenzar. La otra inicializacion posible seria inicializar
Max al valor mas bajo posible.

En cuanto al algoritmo, se puede ver que su complejidad es de orden
cuadratico (aprox: 1/2N^2 + N) y su uso de memoria lineal.
A continuacion intentare busar una aproximacion con un orden de
complejidad menor, y usare este algoritmo para asegurar que los
resultados obtenidos por el nuevo algoritmo son correctos.


SEGUNDA SOLUCION. LA APROXIMACION ESPECIFICA

La solucion anterior se basa en una eleccion aceptablemente buena
para obtener todas las soluciones posibles y elegir de entre todas
la que estamos buscando. Simplemente trata de minimizar el numero
de operaciones reutilizando las que ya hemos realizado al mismo
tiempo que intenta no disparar el uso de memoria al almacenar los
resultados parciales analizando que resultados parciales son
realmente utiles. Ahora bien, el algoritmo anterior no hace un
analisis en profunidad del problema que intentamos resolver y por
tanto la pregunta que nos tenemos que hacer es: El problema que
estamos intentando solucionar tiene caracteristicas que nos permiten
diseņar un algoritmo mejor que el anterior, osea, por debajo del
orden cuadratico?

Bien, Si nos fijamos en el problema, podemos encontrar las siguientes
cualidades:
  - Si en la lista no hay numeros positivos, el resultado sera el
    menor de los negativos.
  - Si en la lista hay numeros positivos, la solucion debe comenzar
    y terminar por numeros positivos.

De estas dos conclusiones podemos obtener un buen numero de
consluiones extra:

  - Si en la lista hay numeros positivos, si la lista comienza o
    finaliza por numeros negativos, esos numeros nunca formaran parte
    de la solucion
  - Si un numero positivo pertence a la solucion, todos los positivos
    colindantes perteneceran a la solucion.
  - Si en la lista hay positivos y un numero negativo que pertenece a
    la solucion, todos los negativos colindantes perten a la
    solucion
  - Si encontramos un cambio de signo positivo-negativo, o estamos
    al final de la sub-lista solucion, o tanto el grupo positivo como
    el negativo pertenecen a la solucion, o ninguno de los dos
    grupos pertenecen a la solucion.
  - etc. etc.

De todas estas conclusiones podemos diseņar un algoritmo de
complejidad lineal que encuentre la solucion que buscamos: La idea del
algoritmo es la siguiente:

  1) Buscamos el primer positivo mientras apuntamos el negativo mayor
  2) Si no hemos encontrado ningun positivo, el negativo que hayamos
     apuntado como mayor sera la solucion, y hemos terminado, con lo
     que vamos hasta 9
  3) Apuntamos el offset como posible inicio de la solucion
  3) Sumamos todos los positivos hasta encontrar el primer negativo
  4) Apuntamos el offset como posible fin.
  5) Comprobamos si con estos offset_begin y offset_end tenemos un
     sumatorio mayor que el maximo encontrado hasta el momento. Si
     es asi, lo guardamos como maximo temporal
  6) Sumamos todos los negativos hasta el siguiente positivo.
  7) Si no hemos encontrado siguiente positivo, hemos terminado, por
     lo que vamos hasta 9
  8) Sumamos la suma de los negativos a la suma de los positivos
     anteriores. Si es mayor o igual que 0, este subconjunto mejora
     la solucion, por lo que volvemos a 3. Si este subconjunto es
     menor que 0, este subconjunto empeoraria el siguiente sumatorio
     por lo que marcamos el comienzo del siguiente candidato en este
     punto y volvemos hasta 3
  9) Fin!!??

La implementacion de este posible algoritmo de complejidad lineal
seria:


typedef struct _LIST_DATA
{
  DWORD dwSize;
  LPINT pData;
}LIST_DATA,*PLIST_DATA;

void
FindMaxSubListFast(PLIST_DATA lpListData, LPDWORD lpdwStartOffset, LPDWORD
lpdwSize)
{
  DWORD dwOffsetBegin = 0;
  DWORD dwOffsetEnd = 0;
  INT ActualResult = 0;
  DWORD dwResultBegin = 0;
  DWORD dwResultEnd = 0;
  INT ActualMax = 0;

  ActualMax = lpListData->pData[0];
  while(dwOffsetBegin<lpListData->dwSize && lpListData->pData[dwOffsetBegin]<0)
  {
    if(lpListData->pData[dwOffsetBegin] >= ActualMax)
    {
      ActualMax = lpListData->pData[dwOffsetBegin];
      dwResultBegin = dwOffsetBegin;
      dwResultEnd = dwOffsetBegin+1;
    }
    dwOffsetBegin++;
  }
  if(dwOffsetBegin != lpListData->dwSize)
  {
    dwOffsetEnd = dwOffsetBegin;
    do
    {
      while(dwOffsetEnd<lpListData->dwSize && lpListData->pData[dwOffsetEnd]>=0)
      {
        ActualResult += lpListData->pData[dwOffsetEnd++];
      }
      if(ActualResult >= ActualMax)
      {
        ActualMax = ActualResult;
        dwResultBegin = dwOffsetBegin;
        dwResultEnd = dwOffsetEnd;
      }
      while(dwOffsetEnd<lpListData->dwSize && lpListData->pData[dwOffsetEnd]<0)
      {
        ActualResult += lpListData->pData[dwOffsetEnd++];
      }
      if(dwOffsetEnd != lpListData->dwSize)
      {
        if(ActualResult < 0)
        {
          dwOffsetBegin = dwOffsetEnd;
          ActualResult = 0;
        }
      }
    }
    while(dwOffsetEnd != lpListData->dwSize);
  }
  *lpdwStartOffset = dwResultBegin;
  *lpdwSize = dwResultEnd - dwResultBegin;
}

Evidentemente, esta solucion no calcula todos los posibles
resultados, por lo que ahora la pregunta es, falla en algun
caso? En las pruebas que he realizado, que sinceramente no han
sido muchas, los resultados arrojados por los dos algoritmos han
sido exactamente los mismos, y ahora mismo no veo ningun caso en
el que pueda fallar.

Por otro lado, no parece factible encontrar una solucion de un
orden menor que lineal, puesto que necesitas recorrer todos los
valores para asegurar que el resultado es valido. Si esto es asi
las posibles mejoras ya no vendrian de un mejor algoritmo, sino
de la optimizacion de su implementacion, que como he dicho al
principio, es un campo que dejare de lado puesto que considero
que no es un objetivo de este reto.

Sin mas, me despido, esperando los comentarios, y esperando
leer el resto de soluciones.

Un saludo
Miguel