© Jirsak/Shutterstock.com
Cuando se trata de conjuntos de datos, es probable que tengan la forma de una matriz. Y estas matrices a menudo son contiguas. Esto significa que no hay”interrupciones”entre los valores de los datos: se almacenan en un solo bloque de memoria. Este tipo de matriz ocupa un lugar central cuando se trata del clásico Problema de Subarreglo Máximo. Si bien hay algunas formas de abordar este problema, una de las mejores formas de abordarlo es utilizando el algoritmo de Kadane. Si se pregunta cómo usar este algoritmo y cómo encaja en la esfera de la programación dinámica, está en el lugar correcto. Acompáñenos mientras exploramos el algoritmo de Kadane y cómo se usa para resolver el problema del subarreglo máximo.
¿Qué es el problema del subarreglo máximo?
El problema del subarreglo máximo también se conoce como el problema del subarreglo máximo. Problema de subarreglo contiguo. En términos simples, la tarea que presenta este problema es encontrar el subarreglo contiguo máximo dentro de un arreglo, arr[], de tamaño N. Es decir, encontrar la suma máxima posible de sumar enteros en el arreglo sin rupturas entre ellos. Por ejemplo, si tomamos una matriz [4,-1, 2, 1], la suma máxima sería simplemente la suma de todos los números enteros, o 6.
Para conjuntos de datos pequeños, esta puede ser una tarea relativamente simple, y se puede resolver con bastante facilidad utilizando lo que se conoce como el”enfoque de fuerza bruta”. Básicamente, esto significa usar los cálculos más simples a expensas de la eficiencia general. De esta forma, podemos partir del índice 0 y calcular la suma de todos los subarreglos posibles, empezando por el elemento A[0]. Podemos calcular estas sumas de subarreglo comenzando con A[1] y continuando hasta A[n-1], donde n es el tamaño del arreglo. Si llamamos a la suma máxima de un subarreglo el máximo_local en el índice i, podemos calcular todo esto y luego terminar encontrando el máximo de los máximos_locales. Esto nos dará la suma más grande posible, que se puede describir como el máximo_global.
Como es de esperar, esto puede funcionar bastante bien para arreglos muy pequeños, pero es bastante ineficiente para conjuntos de datos más grandes. La complejidad del tiempo es cuadrática, u O(n2), lo que significa que la complejidad aumenta con bastante rapidez al aumentar el tamaño de entrada. Por lo tanto, vamos a necesitar un proceso más eficiente y elegante. Aquí es donde entra en juego la programación dinámica.
¿Cómo puede ayudar la programación dinámica?
La programación dinámica es un enfoque para resolver problemas complicados reduciéndolos a una colección de problemas más simples. Estos problemas más fáciles se resuelven y sus soluciones se almacenan en una estructura de datos como una matriz. Luego se puede acceder a estas soluciones cuando estamos resolviendo el mismo tipo de problema, evitando la necesidad de resolverlos nuevamente y acelerando los cálculos generales.
Sería realmente beneficioso si pudiéramos aplicar los principios de programación dinámica a nuestro Problema de Subarreglo Máximo. Afortunadamente, podemos, y eso es exactamente lo que se propone hacer el algoritmo de Kadane. Entonces, entremos en eso.
La programación dinámica es un enfoque para resolver problemas complicados reduciéndolos a una colección de problemas más simples.
©hafakot/Shutterstock.com
Algoritmo de Kadane
Como se mencionó brevemente, el algoritmo de Kadane usa programación dinámica para calcular una solución eficiente al Problema del subarreglo máximo. El algoritmo funciona almacenando el subarreglo contiguo de suma máxima en el índice actual. Luego se compara con la suma máxima encontrada hasta ahora. Si es mayor que la suma máxima encontrada hasta el momento, se actualiza con el nuevo valor.
Una de las principales ventajas del algoritmo de Kadane es su velocidad, que se muestra en su complejidad temporal de O(n). Esto significa que la complejidad temporal aumenta linealmente con el aumento del tamaño de entrada, lo que es mucho mejor que la complejidad temporal cuadrática del enfoque de fuerza bruta. La complejidad del espacio también es buena, ya que el algoritmo es estable; esto significa que se requiere una cantidad constante de memoria durante el proceso, ya que solo se deben almacenar dos variables (estas son global_maximum y local_maximum).
Algoritmo de Kadane en acción
Tomemos la matriz [4,-1, 2, 1] nuevamente. Si invertimos el enfoque de fuerza bruta y comenzamos con el elemento A[n] (en este caso, 1), podemos calcular la suma de cada subarreglo posible y luego continuar con A[n-1], A[n-2] hasta que los hayamos completado todos.
Observando los dos últimos elementos, A[3] y A[4], podemos ver que el local_maximum es 5 y 6 respectivamente. Pero, si conocemos local_maximum[3], no necesitamos calcular todas las sumas de subarreglo para A[4]. Esto se debe a que ya conocemos los resultados de A[3] y el local_maximum[3]. Solo necesitamos verificar dos subarreglos, el que contiene solo A[4] y la suma de A[4] y local_maximum[3]. En este caso, esto sería A[4} + local_maximum[3], que es 6. Esta es la misma respuesta que obtenemos si calculamos todas las sumas de subarreglo para A[4].
Este principio es lo que sustenta el algoritmo de Kadane, y se puede describir de la siguiente manera:
local_maximum[i]=max(A[i], A[i] + local_maximum[i-1])
O, en otras palabras, el máximo_local en el índice i es el máximo de A[i] y la suma de A[i] y el máximo_local en el índice i-1.
Entonces, solo necesitamos encontrar el máximo de A[i] y A[i] + local_maximum[i-1] para encontrar el máximo en cada índice i. Por lo tanto, solo necesitamos encontrar cada local_maximum para encontrar el subarreglo máximo. Esta es una forma mucho más eficiente de abordar el problema del subarreglo máximo.
El funcionamiento del algoritmo de Kadane
Repasemos los pasos que utiliza el algoritmo de Kadane para calcular el subarreglo máximo.
El algoritmo requerirá solo un bucle, iterando desde i[0[ hasta i[n-1]. El local_maximum[i] se calculará para cada elemento, que depende del local_maximum[i-1]. El local_maxium se compara al máximo_global. Si es mayor, se actualizará global_maximum. Esto se repite para cada índice hasta que se encuentre la suma más grande de un subarreglo contiguo.
Implementación del algoritmo de Kadane
Para mostrar cómo se puede implementar el algoritmo de Kadane, vamos a utilizar Python en el entorno de Spyder. Echemos un vistazo a cómo funciona el código en la práctica.
from sys import maxsize def solveMaxSubArrayProblem(input): n=len(input) globalMaxSum=-maxsize-1 localMaxSum=0 for i in range(0, n): localMaxSum=max(entrada[i], entrada[i] + localMaxSum) if(localMaxSum>globalMaxSum): globalMaxSum=localMaxSum return globalMaxSum if_name_==”_main_”entrada=[1,-2, 5,-3, 4,-1, 6] result=solveMaxSubArrayProblem(input) print(result) 11
En primer lugar, la sangría adecuada en Python es clave para ejecutar el código correctamente. Para comenzar, estamos importando la función”maxsize”, que se usa para encontrar el valor máximo.
A continuación, estamos definiendo”solveMaxSubArrayProblem”como una función de la matriz”input”de longitud n , con globalMaxSum inicializado como el valor entero mínimo. Esto se hace para garantizar que la suma de cualquier subarreglo calculado sea mayor que este valor.
El máximo_local variará y se establece inicialmente en 0.
“for” se refiere a un ciclo, que se utiliza para iterar a través de cada elemento de la matriz.
Para cada iteración,”localMaxSum”se actualiza a la localMaxSum del elemento actual o al elemento más la localMaxSum anterior.
Si localMaxSum es mayor que el globalMaxSum actual, este último se actualiza para reflejar este cambio.
Una vez que se completa el proceso iterativo, globalMaxSum es igual al subarreglo contiguo máximo y se devuelve este resultado.
Por último,”if __name__==””__main__””prueba la función creando la matriz que sigue y usando la función definida en ella, y luego imprime el resultado.
Para la matriz [1 ,-2, 5,-3, 4,-1, 6], el subarreglo contiguo máximo tiene una suma de 11.
©”TNGD”.com
Conclusión
Cubrimos el principio detrás de la programación dinámica. También mostramos cómo el algoritmo de Kadane usa esto para resolver el problema del subarreglo máximo. Se describieron las ventajas de esto. El algoritmo de Kadane es relativamente simple de entender y usar, con una complejidad de tiempo y espacio eficiente. Cuando se trata de resolver el problema del subarreglo máximo, el algoritmo de Kadane es una de las formas más rápidas de hacerlo.
A continuación…
Algoritmo de Kadane: un enfoque eficiente del problema del subarreglo máximo , Explicado con fotos Preguntas frecuentes (FAQ)
¿Qué es un subarreglo?
Un subarreglo es parte de un arreglo ininterrumpido, es decir, sin interrupciones entre enteros. Esto se describe como contiguo. Un subarreglo puede constar de un elemento. Se utilizan principalmente cuando se trabaja con conjuntos de datos, para hacer cosas como encontrar el subarreglo contiguo máximo.
¿Qué es la programación dinámica?
La programación dinámica se refiere a una técnica para resolver problemas complejos dividiéndolos en otros más simples. Cada subsolución solo debe calcularse una vez y se almacena en un caché temporal. De esta forma, se evitan los cálculos redundantes, por lo que los procesos se aceleran significativamente. La programación dinámica se usa a menudo para optimizar soluciones y diseñar algoritmos, como el algoritmo Bellman-Ford para encontrar la ruta más corta en un gráfico. Por lo general, los subproblemas se resuelven de abajo hacia arriba, lo que significa que los problemas más simples se resuelven primero. Estas soluciones luego se combinan para resolver el problema inicial.
¿Cuál es el problema del subarreglo máximo?
Este es un problema de programación clásico que consiste en encontrar la suma más grande subarreglo contiguo dentro de un arreglo de enteros. La solución a este problema tiene múltiples aplicaciones, en campos como las finanzas, el análisis de datos y el procesamiento de señales. El algoritmo más eficiente para resolver esto es el algoritmo de Kadane.
¿Qué es el algoritmo de Kadane?
El algoritmo de Kadane es un enfoque eficiente para resolver el problema de subarreglo máximo contiguo. El algoritmo funciona calculando el máximo_local y el máximo_global. Al iterar sobre la matriz que comienza desde la izquierda, estas variables se actualizan en cada paso, con el máximo local_maximum hasta ahora reemplazando al global_maximum si su valor es mayor. Una vez que se han calculado todos los máximos_locales, se conoce el subarreglo contiguo máximo y se iguala al máximo_global.
¿Cuál es el enfoque de fuerza bruta para resolver el problema del subarreglo máximo?
El enfoque de fuerza bruta implica iterar sobre todos los subarreglos posibles en un arreglo y calcular las sumas de los subarreglos. Entonces se puede encontrar el subarreglo contiguo máximo, pero el proceso no es muy eficiente ya que se debe calcular cada subarreglo.
¿Cuáles son las desventajas de usar el algoritmo de Kadane?
Aunque el algoritmo de Kadane es simple y eficiente, en realidad solo se puede usar para resolver el problema del subarreglo máximo. La salida que produce también está limitada, ya que solo contiene la suma del subarreglo máximo. No se proporciona información sobre la matriz en sí, lo que puede ser necesario para algunas aplicaciones. Por último, si bien el algoritmo es rápido, la solución no es óptima en todos los casos.
¿Cuál es la complejidad temporal del algoritmo de Kadane?
La complejidad temporal de El algoritmo de Kadane es O(n).
¿Se puede usar el algoritmo de Kadane con matrices no contiguas?
No, el algoritmo no se puede usar con matrices no contiguas.
¿Cómo se puede modificar el algoritmo de Kadane para encontrar el subarreglo con la suma mínima?
Simplemente podemos sustituir la función maxsize por minsize e inicialice las variables hasta el infinito en lugar de cero.
¿Se puede usar el algoritmo de Kadane con una matriz con todos los enteros negativos?
Sí, el algoritmo devuelve el subarreglo con la menor suma negativa en este caso.