si estás aquí, entonces lo más probable es que estabas tratando de resolver el «problema de Subarrays máximo» y se encontró con el algoritmo de Kadane, pero no podía averiguar cómo algo así está funcionando. O tal vez estabas cansado de usar el algoritmo de Kadane como una «caja negra». O tal vez usted quería entender el aspecto de programación dinámica de la misma. O tal vez solo quieres aprender sobre un nuevo concepto que puede hacerte mejor en la programación. Cualquiera que sea la razón, has venido al lugar correcto.,
para entender mejor el algoritmo de Kadane, primero, pasaríamos por una breve introducción de la programación dinámica. Entonces, nos fijaríamos en un problema de programación bastante popular, el problema de Subarray máximo. Veríamos cómo se puede resolver este problema usando un enfoque de fuerza bruta y luego intentaríamos mejorar nuestro enfoque y llegar a un algoritmo mejor, también conocido como el algoritmo de Kadane.
Así que, vamos a entrar en ella.,
programación dinámica
la Programación Dinámica es un método para resolver un problema complejo descomponiéndolo en una colección de subproblemas más simples, resolviendo cada uno de esos subproblemas una sola vez y almacenando sus soluciones utilizando una estructura de datos basada en memoria (matriz, mapa, etc.). Así que la próxima vez que se produce el mismo sub-problema, en lugar de volver a calcular su solución, uno simplemente busca la solución previamente calculada, ahorrando así tiempo de cálculo.
Aquellos que no pueden recordar el pasado están condenados a repetirlo., — Programación dinámica
Aquí hay una brillante explicación sobre el concepto de programación dinámica en Quora-respuesta de Jonathan Paulson A Cómo debo explicar la programación dinámica a un niño de 4 años?
aunque hay más en la programación dinámica, nos moveríamos hacia adelante para entender el problema de Subarray máximo.
problema de Subarrays máximo
el problema de subarrays máximo es la tarea de encontrar la suma más grande posible de un subarrays contiguo, dentro de una matriz unidimensional dada A de números.,
Por ejemplo, para la matriz anterior, la contiguos subarray con la mayor suma es , con la suma de 6. Usaríamos esta matriz como nuestro ejemplo para el resto de este artículo. Además, asumiríamos que este array está indexado a cero, es decir, -2 sería llamado como el elemento’ 0th ‘ del array y así sucesivamente. Además, a representaría el valor en el índice i.,
ahora, echaríamos un vistazo a una solución muy obvia para el problema dado.
aproximación de fuerza bruta
una solución muy obvia pero no tan buena es calcular la suma de cada subarray posible y el máximo de esos sería la solución. Podemos comenzar desde el índice 0 y calcular la suma de todos los subarrays posibles comenzando con el elemento A, como se muestra en la siguiente figura. Entonces, calcularíamos la suma de cada subarray posible comenzando con A, A y así sucesivamente hasta A, donde n denota el tamaño de la matriz (n = 9 en nuestro caso)., Tenga en cuenta que cada elemento es un subarray en sí.
vamos a llamar a la suma máxima de subarrays comenzando con el elemento a la local_maximum en el índice i. Así, después de ir a través de todos los índices, se quedaría con local_maximum para todos los índices. Finalmente, podemos encontrar el máximo de estos local_maximums y obtendremos la solución final, i. e., la suma máxima posible. Podríamos llamar a esto la global_maximum.
pero puede notar que este no es un método muy bueno porque a medida que aumenta el tamaño de la matriz, el número de posibles subarrays aumenta rápidamente, aumentando así la complejidad computacional. O para ser más precisos, si el tamaño de la matriz es n, entonces la complejidad temporal de esta solución es O(n2) que no es muy buena.
¿Cómo podemos mejorar esto? ¿Hay alguna manera de utilizar el concepto de programación dinámica? Averigüémoslo.,
algoritmo de Kadane
en esta sección, usaríamos el enfoque de fuerza bruta discutido anteriormente de nuevo, pero esta vez comenzaríamos hacia atrás. ¿Cómo ayudaría eso? Veamos.
empezaríamos desde el último elemento y calcularíamos la suma de cada subarray posible que termina con el elemento A, como se muestra en la siguiente figura. Entonces, calcularíamos la suma de cada subarray posible que termina con A, A y así sucesivamente hasta A.,
Ahora vamos a centrarnos en los subarrays terminando con el elemento a (=-1) y (=2) se muestra en la siguiente figura.,
a partir De la figura anterior, vemos que el local_maximum es igual a 3, que es la suma de los subarray . Ahora eche un vistazo a los subarrays que terminan con A. notará que estos subarrays se pueden dividir en dos partes, los subarrays que terminan con a (resaltados con amarillo) y el subarrays de un solo elemento A (en verde).
digamos que de alguna manera conozco el local_maximum., Entonces vemos que para calcular el local_maximum, no necesitamos calcular la suma de todos los subarrays que terminan con A ya que ya sabemos el resultado de los arrays que terminan con A. tenga en cuenta que si array tenía la suma máxima, entonces solo necesitamos verificar los arrays resaltados con las flechas rojas para calcular local_maximum. Y esto nos lleva al principio en el que funciona el algoritmo de Kadane.
local_maximum en el índice i es el máximo de a y la suma de a y local_maximum en el índice i-1.,
Usando el método anterior, necesitamos iterar a través de la matriz de una sola vez, lo cual es mucho mejor que el anterior acercamiento de fuerza bruta. O para ser más precisos, la complejidad temporal del algoritmo de Kadane es O (n).
finalmente, veamos cómo funcionaría todo esto en código.,
Code Walkthrough
a continuación se muestra una implementación muy autoexplicativa (en C++) de una función que toma un array como argumento y devuelve la suma del subarrays máximo.
tenga en cuenta que en lugar de utilizar una matriz para almacenar local_maximums, estamos, simplemente, almacenar la última local_maximum en una variable de tipo int ‘local_max’, porque eso es lo que necesitamos para calcular la siguiente local_maximum., Además, como estamos usando una variable ‘global_max’ para realizar un seguimiento del valor máximo de local_maximum, que al final resulta ser la salida requerida.
conclusión
debido a la forma en que este algoritmo utiliza subestructuras óptimas (el subarray máximo que termina en cada posición se calcula de una manera simple a partir de un subproblema relacionado pero más pequeño y superpuesto: el subarray máximo que termina en la posición anterior) este algoritmo puede ser visto como un simple ejemplo de programación dinámica., El algoritmo de Kadane es capaz de encontrar la suma máxima de un subarray contiguo en una matriz con un tiempo de ejecución de O(n).