algorithm
Algoritmo de subarray máximo

Información básica del algoritmo de subarray máximo

El problema de subarray máximo es el método para encontrar el subarray contiguo dentro de una matriz unidimensional de números que tiene la suma más grande.

El problema fue propuesto originalmente por Ulf Grenander de la Brown University en 1977, como un modelo simplificado para la estimación de máxima probabilidad de patrones en imágenes digitalizadas.

Podemos resolver este problema, consideremos una lista de varios enteros. Podríamos estar interesados ​​en cuál subconjunto completamente adyacente tendrá la mayor suma. Por ejemplo, si tenemos la matriz [0, 1, 2, -2, 3, 2] , el subarreglo máximo es [3, 2] , con una suma de 5 .

Enfoque de fuerza bruta para la solución:

Este método es el más ineficiente para encontrar la solución. En esto, terminaremos repasando cada posible subarreglo, y luego encontraremos la suma de todos ellos. Por fin, compare todos los valores y averigüe el subarray máximo.

Pseudo código para el enfoque de fuerza bruta:

MaxSubarray(array)
  maximum = 0
  for i in input
    current = 0
    for j in input
       current += array[j]
       if current > maximum
         maximum = current
  return maximum

La complejidad del tiempo para el método de fuerza bruta es O(n^2) . Así que vamos a pasar a dividir y conquistar el enfoque.

Divide y conquista el enfoque para la solución:

Encuentra la suma de los subarrays en el lado izquierdo, los subarrays en el lado derecho. Luego, eche un vistazo a todos los que cruzan la división del centro y finalmente devuelva la suma máxima. Debido a que este es un algoritmo de dividir y conquistar, necesitamos tener dos funciones diferentes.

Lo primero es dividir paso,

maxSubarray(array)
  if start = end
    return array[start]
  else
    middle = (start + end) / 2
    return max(maxSubarray(array(From start to middle)), maxSubarray(array(From middle + 1 to end)), maxCrossover(array))

En la segunda parte, separe las diferentes partes que se crean en la primera parte.

maxCrossover(array)
  currentLeftSum = 0
      leftSum = 0
  currentRightSum = 0
      rightSum = 0
  for i in array
    currentLeftSum += array[i]
    if currentLeftSum > leftSum
      leftSum = currentLeftSum
  for i in array
    currentRightSum += array[i]
    if currentRightSum > rightSum
      rightSum = currentRightSum
  return leftSum + rightSum

La complejidad del tiempo para el método de Dividir y Conquistar es O(nlogn) . Así que vamos a pasar al enfoque de la programación dinámica.

Enfoque de programación dinámica:

Esta solución también se conoce como algoritmo de Kadane. Es un algoritmo de tiempo lineal. Esta solución es dada por Joseph B. Kadane a finales de los 70.

Este algoritmo solo pasa por el bucle, cambiando continuamente la suma máxima actual. Curiosamente, este es un ejemplo muy simple de un algoritmo de programación dinámico, ya que toma un problema de superposición y lo reduce para que podamos encontrar una solución más eficiente.

Pseudo código del algoritmo de Kadane:

MaxSubArray(array)
  max = 0
  currentMax = 0
  for i in array
    currentMax += array[i]
    if currentMax < 0
      currentMax = 0
    if max < currentMax
      max = currentMax
  return max

La complejidad del tiempo para el algoritmo de Kadane es O(n) .

Implementación de C #

public class MaximumSubarray
{
    private static int Max(int a, int b)
    {
        return a > b ? a : b;
    }

    static int MaxSubArray(int[] input, int n)
    {
        int max = input[0];
        int currentMax = input[0];
        for (int i = 1; i < n; i++)
        {
            currentMax = Max(input[i], currentMax + input[i]);
            max = Max(max, currentMax);
        }
        return max;
    }

    public static int Main(int[] input)
    {
        int n = input.Length;
        return MaxSubArray(input, n);
    }
}