Es un problema en el cuál queremos obtener, de una lista de números, la parte de la lista en donde la suma de los elementos de la lista es la más grande de toda la lista.
Se le llama "arreglo" debido a que así lo llama la computadora. A una lista de números se le llama arreglo. Un sub-arreglo es una parte de esa lista.
Bueno, hay varias formas de hacerlo. Quizá ya te hayas imaginado esa forma, por eso aquí te la presentamos. Esto que verás aquí es un código que tu computadora puede entender (JavaScript) y el cual ejecutará para resolver este problema.
Da click sobre cada forma para ver su respectivo código fuente o ingresa valores y da click sobre la forma que quieres usar para resolver el problema.
Imagina que el arreglo tiene muchísimos números. Ambas formas llegarán al resultado, sin embargo, la forma óptima lo hará en menos tiempo si lo comparamos con la forma normal.
¡Pruebalo tu mismo! Escoge el número de ceros y ve como la forma normal tarda menos que la forma rápida. Esta prueba no se verá de forma animada porque es demasiado trabajo para tu computadora. La computadora ejecutará ambos algoritmos al mismo tiempo.
Cantidad de números (generados aleatoriamente) a probar: 1000
Cuidado: el tiempo varia de dispositivo a dispositivo. El mínimo es 1K y el máximo 1M.
add clear ¡Resolver!Porque la forma optimizada esta diseñada usando el paradigma de "Divide y vencerás". Este paradigma dice que un problema se debe de dividir en subproblemas más pequeños hasta que la solución al problema sea trivial. Después se vuelven a unir todas las soluciones hasta que se obtenga la solución al problema original, además de que los problemas no deben de solaparse entre sí.
En otras palabras, el arreglo de números se divide en muchas partes pequeñitas hasta que cada arreglo consta de un sólo número. Después, se van sumando los elementos de cada arreglo de un elemento de tamaño y se va encontrando el arreglo más grande. Así se sigue hasta encontrar el arreglo con la suma más grande.
En el análisis de imágenes, cuando se trata de encontrar el área más brillante de una imagen, se ocupa este algoritmo. La imagen debe de ser un mapa de bits (archivos con extensión .bmp). La imagen se transforma en una matriz en la que cada valor equivale al brillo de cada pixel.
Ese es el uso más fácil de entender. Sin embargo no es el único, también en el análisis de las subsecuencias genómicas y en la minería de datos de utiliza este algoritmo. En el ejemplo que ves en esta página se utilizan valores positivos y negativos, en los usos de la vida real que ya te mostramos se utiliza otro rango de valores.
Eso es todo por hoy 😁 ahora es tu turno: ¿Qué fue lo que entendiste? ¿Entendiste el algoritmo?
Creado para la materia de análisis de algoritmos por: