Hoy vamos a hablar de desarrollo web en particular. Ni de nada relacionado con las últimas tecnologías de programación. Vamos a estudiar varios algoritmos de cálculo del subarray máximo, en mi opinión, muy bonitos. Pero primero planteemos el problema:

Se trata del problema del subarray máximo: Tenemos un array numérico que incluye valores tanto positivos como negativos. Queremos saber cuál es su subarray, de elementos contiguos, cuya suma de sus elementos nos da un valor máximo. Por ejemplo, supongamos el siguiente array:

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Su subarray máximo sería (en índices basados en cero) el que va de la posición 3 a la 6:

[4, -1, 2, 1]

Cuyo resultado nos da 6.

Tómate un minuto para esbozar sobre papel un algoritmo que resuelva este problema. O al menos trata de esbozarlo mentalmente. Cuando hayas terminado, continúa leyendo.

Lo más probable es que hayas llegado a una solución de complejidad cuadrática O(n²), o dicho mal y rápido: un bucle dentro de otro bucle. Vamos a ver una posible solución de este tipo en PHP:

function max_subarray($array) {
   $max = 0;

   for ($i = 0; $i < count($array); $i++) {
      $sum = 0;
      for ($j = $i; $j < count($array); $j++) {
         $sum += $array[$j];
         if ($sum > $max) {
            $max = $sum;
         }
      }
   }
   return $max;
}

Es decir, es una solución de fuerza bruta con la que calculamos todas las sumas posibles de todos los subarrays que podemos extraer del array principal. Este algoritmo está bien. Es sencillo, eficiente, su resultado es siempre correcto; pero los hay mejores.

Podemos resolverlo mediante un enfoque recursivo mediante la técnica de divide-y-vencerás, obteniendo una complejidad del tipo O(n log n). Pero, ¿y si te digo que lo puedes resolver mediante un algoritmo lineal de O(n)? ¿Te animas a demostrarte a ti mismo lo buen programador que eres? Pista: la clave está en las sumas inferiores a cero.

Vamos a ver la solución:

function max_subarray2($A) {
   $mejorHastaAhora = $mejorDeAhora = 0;

   for ($i = 0; $i<count($A); $i++) {
      $mejorDeAhora += $A[$i];
      if ($mejorDeAhora < 0) {
         $mejorDeAhora = 0;
      }
      if ($mejorDeAhora > $mejorHastaAhora) {
         $mejorHastaAhora = $mejorDeAhora;
      }
   }

   return $mejorHastaAhora;
}

Tenemos dos contadores:

  1. mejorDeAhora, que lleva la suma parcial en curso.
  2. mejorDeTodos, que almacena el mejor resultado de todos los calculados. Si mejorDeAhora es superior a mejorDeTodos, actualizamos este último.

Como decíamos, la clave está en las sumas inferiores a cero: cada vez que una suma parcial baje de cero, reiniciamos el sumatorio “mejorDeAhora”: Recuerda que una de las precondiciones era que hubiera tanto números positivos como negativos, luego alguna suma de uno o más elementos debe ser superior a cero.

Si además hacemos uso de la función max() disponible en la mayoría de lenguajes de programación, nos quedaría así de sencillo:

function max_subarray3($A) {
   $mejor = $sumatorio = 0;
   for ($i = 0; $i<count($A); $i++) {
      $sumatorio = max($sumatorio+$A[$i], 0);
      $mejor = max($sumatorio, $mejor);
   }
   return $mejor;
}

Y así es como, mediante un poco de ingenio, hemos pasado de tener una función de orden cuadrático a orden lineal. Puedes hacerte una idea del impacto en rendimiento que puede tener esto en grandes volúmenes de datos.

¡Esperamos que hayas disfrutado de este post!