1. Información general
El problema del subarreglo máximo es una tarea para encontrar la serie de elementos contiguos con la suma máxima en cualquier arreglo dado.
Por ejemplo, en la siguiente matriz, la submatriz resaltada tiene la suma máxima (6):
En este tutorial, veremos dos soluciones para encontrar el subarreglo máximo en un arreglo . Uno de los cuales diseñaremos con O (n) complejidad temporal y espacial.
2. Algoritmo de fuerza bruta
La fuerza bruta es un enfoque iterativo para resolver un problema. En la mayoría de los casos, la solución requiere varias iteraciones sobre una estructura de datos. En las siguientes secciones, aplicaremos este enfoque para resolver el problema de subarreglo máximo.
2.1. Acercarse
En general, la primera solución que se nos ocurre es calcular la suma de todos los subarreglos posibles y devolver el que tenga la suma máxima.
Para empezar, calcularemos la suma de cada subarreglo que comienza en el índice 0. Y de manera similar, encontraremos todos los subarreglos comenzando en cada índice de 0 a n-1 donde n es la longitud del arreglo:
Entonces, comenzaremos en el índice 0 y agregaremos cada elemento a la suma acumulada en la iteración. También realizaremos un seguimiento de la suma máxima vista hasta ahora . Esta iteración se muestra en el lado izquierdo de la imagen de arriba.
En el lado derecho de la imagen, podemos ver la iteración que comienza en el índice 3 . En la última parte de esta imagen, tenemos el subarreglo con la suma máxima entre el índice 3 y 6 .
Sin embargo, nuestro algoritmo continuará encontrando todos los subarreglos a partir de índices entre 0 y n-1 .
2.2. Implementación
Veamos ahora cómo podemos implementar esta solución en Java:
public int maxSubArray(int[] nums) { int n = nums.length; int maximumSubArraySum = Integer.MIN_VALUE; int start = 0; int end = 0; for (int left = 0; left < n; left++) { int runningWindowSum = 0; for (int right = left; right maximumSubArraySum) { maximumSubArraySum = runningWindowSum; start = left; end = right; } } } logger.info("Found Maximum Subarray between {} and {}", start, end); return maximumSubArraySum; }Como era de esperar, actualizamos maximumSubArraySum si la suma actual es mayor que la suma máxima anterior. En particular, también actualizamos el inicio y el final para averiguar las ubicaciones de índice de este subarreglo .
2.3. Complejidad
En términos generales, la solución de fuerza bruta itera sobre la matriz muchas veces para obtener todas las soluciones posibles. Esto significa que el tiempo que tarda esta solución crece de forma cuadrática con el número de elementos de la matriz. Esto puede no ser un problema para arreglos de tamaño pequeño. Pero a medida que aumenta el tamaño de la matriz, esta solución no es eficiente.
Al inspeccionar el código, también podemos ver que hay dos bucles for anidados . Por tanto, podemos concluir que la complejidad temporal de este algoritmo es O (n2) .
En las secciones posteriores, resolveremos este problema en complejidad O (n) usando programación dinámica.
3. Programación dinámica
La programación dinámica resuelve un problema dividiéndolo en subproblemas más pequeños. Esto es muy similar a la técnica de resolución del algoritmo divide y vencerás. Sin embargo, la principal diferencia es que la programación dinámica resuelve un subproblema solo una vez.
Luego almacena el resultado de este subproblema y luego reutiliza este resultado para resolver otros subproblemas relacionados. Este proceso se conoce como memorización .
3.1. Algoritmo de Kadane
El algoritmo de Kadane es una solución popular para el problema del subarreglo máximo y esta solución se basa en la programación dinámica.
El desafío más importante para resolver un problema de programación dinámica es encontrar los subproblemas óptimos .
3.2. Acercarse
Entendamos este problema de una manera diferente:
En la imagen de arriba, asumimos que el subarreglo máximo termina en la última ubicación del índice. Por lo tanto, la suma máxima de subarreglos será:
maximumSubArraySum = max_so_far + arr[n-1]max_so_far es la suma máxima de un subarreglo que termina en el índice n-2 . Esto también se muestra en la imagen de arriba.
Ahora, podemos aplicar esta suposición a cualquier índice de la matriz. Por ejemplo, la suma máxima de subarreglos que termina en n-2 se puede calcular como:
maximumSubArraySum[n-2] = max_so_far[n-3] + arr[n-2]Por tanto, podemos concluir que:
maximumSubArraySum[i] = maximumSubArraySum[i-1] + arr[i]Ahora, dado que cada elemento de la matriz es una submatriz especial de tamaño uno, también debemos verificar si un elemento es mayor que la suma máxima en sí:
maximumSubArraySum[i] = Max(arr[i], maximumSubArraySum[i-1] + arr[i])Al observar estas ecuaciones, podemos ver que necesitamos encontrar la suma máxima de subarreglos en cada índice del arreglo. Por lo tanto, dividimos nuestro problema en n subproblemas. Podemos encontrar la suma máxima en cada índice iterando la matriz solo una vez:
El elemento resaltado muestra el elemento actual en la iteración. En cada índice, aplicaremos la ecuación derivada anteriormente para calcular un valor para max_ending_here . Esto nos ayuda a identificar si debemos incluir el elemento actual en el subarreglo o comenzar un nuevo subarreglo comenzando en este índice .
Another variable, max_so_far is used to store the maximum subarray sum found during the iteration. Once we iterate over the last index, max_so_far will store the sum of the maximum subarray.
3.3. Implementation
Again, let's see how we can now implement the Kadane algorithm in Java, following the above approach:
public int maxSubArraySum(int[] arr) { int size = arr.length; int start = 0; int end = 0; int maxSoFar = 0, maxEndingHere = 0; for (int i = 0; i maxEndingHere + arr[i]) { start = i; maxEndingHere = arr[i]; } else maxEndingHere = maxEndingHere + arr[i]; if (maxSoFar < maxEndingHere) { maxSoFar = maxEndingHere; end = i; } } logger.info("Found Maximum Subarray between {} and {}", start, end); return maxSoFar; }Here, we updated the start and end to find the maximum subarray indices.
3.4. Complexity
Since we only need to iterate the array once, the time complexity of this algorithm is O(n).
So as we can see, the time taken by this solution grows linearly with the number of elements in the array. Consequently, it is more efficient than the brute force approach we discussed in the last section.
4. Conclusion
En este tutorial rápido, hemos descrito dos formas de resolver el problema de subarreglo máximo.
Primero, exploramos un enfoque de fuerza bruta y vimos que esta solución iterativa daba como resultado un tiempo cuadrático. Más tarde, discutimos el algoritmo de Kadane y usamos programación dinámica para resolver el problema en tiempo lineal.
Como siempre, el código fuente completo del artículo está disponible en GitHub.