El problema del subarreglo máximo es lo mismo que el problema del segmento máximo. Este tutorial analiza el problema con la codificación en C++. La pregunta es: ¿cuál es la suma máxima de cualquier secuencia posible de números consecutivos dentro de una matriz? Esto puede significar toda la matriz. Este problema y su solución en cualquier idioma, se conoce como el Problema de Máxima Sub-Matriz. La matriz puede tener posibles números negativos.
La solución tiene que ser eficiente. Necesita tener la complejidad de tiempo más rápida. A partir de ahora, el algoritmo más rápido para la solución se conoce en la comunidad científica como el Algoritmo de Kadane. Este artículo explica el algoritmo de Kadane con C++.
Ejemplos de datos
Considere el siguiente vector (matriz):
vector < En t > un = { 5 , - 7 , 3 , 5 , - 2 , 4 , - 1 } ;
El segmento (sub-arreglo) con la suma máxima es la secuencia, {3, 5, -2, 4}, que da una suma de 10. Ninguna otra secuencia posible, incluso la matriz completa, dará una suma de hasta el valor de 10. Toda la matriz da una suma de 7, que no es la suma máxima.
Considere el siguiente vector:
vector < En t > B = { - 2 , 1 , - 3 , 4 , - 1 , 2 , 1 , - 5 , 4 } ;
El segmento (sub-arreglo) con la suma máxima es la secuencia, {4, −1, 2, 1} que da una suma de 6. Tenga en cuenta que puede haber números negativos dentro del subarreglo para la suma máxima.
Considere el siguiente vector:
vector < En t > C = { 3 , 2 , - 6 , 4 , 0 } ;
El segmento (sub-arreglo) con la suma máxima es la secuencia, {3, 2} que da una suma de 5.
Considere el siguiente vector:
vector < En t > re = { 3 , 2 , 6 , - 1 , 4 , 5 , - 1 , 2 } ;
El subarreglo con la suma máxima es la secuencia, {3, 2, 6, -1, 4, 5, -1, 2} que da una suma de 20. Es el arreglo completo.
Considere el siguiente vector:
vector < En t > mi = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , 15 , 4 , - 8 , - 15 , - 22 } ;
Aquí hay dos subarreglos con sumas máximas. La suma mayor es la que se considera como solución (respuesta) para el problema del máximo subarreglo. Los sub-arreglos son: {5, 7} con una suma de 12, y {6, 5, 10, -5, 15, 4} con una suma de 35. Por supuesto, la rebanada con la suma de 35, es la respuesta.
Considere el siguiente vector:
vector < En t > F = { - 4 , 10 , 15 , 9 , - 5 , - 20 , - 3 , - 12 , - 3 , 4 , 6 , 3 , 2 , 8 , 3 , - 5 , - 2 } ;
Hay dos subarreglos con sumas máximas. La suma mayor es la que se considera como solución para el problema del máximo subarreglo. Los subconjuntos son: {10, 15, 9} con una suma de 34, y {4, 6, 3, 2, 8, 3} con una suma de 26. Por supuesto, la rebanada con la suma de 34 es la respuesta porque el problema es buscar el subarreglo de mayor suma y no el subarreglo de mayor suma.
Desarrollo del algoritmo de Kadane
La información en esta sección del tutorial no es el trabajo original de Kadane. Es la manera propia del autor de enseñar el algoritmo de Kadane. Uno de los vectores anteriores, con sus totales acumulados, está en esta tabla:
| Datos | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | 15 | 4 | -8 | -15 | -22 |
| Total corriente | 5 | 12 | 8 | -2 | -8 | -2 | 3 | 13 | 8 | 23 | 27 | 21 | 16 | -6 |
| índice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
El total acumulado de un índice es la suma de todos los valores anteriores, incluido el del índice. Hay dos secuencias con sumas máximas aquí. Son {5, 7}, que da una suma de 12, y {6, 5, 10, -5, 15, 4}, que da una suma de 35. La secuencia que da una suma de 35 es la que se desea .
Tenga en cuenta que para los totales acumulados, hay dos picos que son los valores 12 y 27. Estos picos corresponden a los últimos índices de las dos secuencias.
Entonces, la idea del algoritmo de Kadane es hacer el total acumulado mientras se comparan las sumas máximas a medida que se encuentran, moviéndose de izquierda a derecha en la matriz dada.
Otro vector de arriba, con sus totales acumulados, está en esta tabla:
Hay dos secuencias con sumas máximas. Son {10, 15, 9}, lo que da una suma de 34; y {4, 6, 3, 2, 8, 3} que da una suma de 26. La secuencia que da la suma de 34, es lo que se desea.
Observe que para los totales acumulados, hay dos picos que son los valores 30 y 13. Estos picos corresponden a los últimos índices de las dos secuencias.
Nuevamente, la idea del algoritmo de Kadane es hacer el total acumulado mientras se comparan las sumas máximas a medida que se encuentran, moviéndose de izquierda a derecha en la matriz dada.
Código por el Algoritmo de Kadane en C++
El código proporcionado en esta sección del artículo no es necesariamente el que usó Kadane. Sin embargo, es por su algoritmo. El programa, como muchos otros programas de C++, comenzaría con:
#incluir#include
utilizando el espacio de nombres estándar;
Se incluye la biblioteca iostream, que es responsable de la entrada y la salida. Se utiliza el espacio de nombres estándar.
La idea del algoritmo de Kadane es tener el total acumulado mientras se comparan las sumas máximas a medida que se encuentran, moviéndose de izquierda a derecha en la matriz dada. La función para el algoritmo es:
int maxSunArray ( vector < En t > & A ) {int N = tamaño A ( ) ;
int maxSuma = A [ 0 ] ;
int ejecutarTotal = A [ 0 ] ;
por ( En t i = 1 ; i < NORTE; yo ++ ) {
int tempRunTotal = runTotal + A [ i ] ; // podría ser más pequeño que A [ i ]
si ( A [ i ] > tempRunTotal )
ejecutarTotal = A [ i ] ; // en caso A [ i ] es mayor que el total acumulado
más
ejecutarTotal = tempEjecutarTotal;
si ( correrTotal > cantidad máxima ) // comparando todas las sumas máximas
maxSum = ejecutarTotal;
}
devolver cantidad maxima;
}
Se determina el tamaño, N de la matriz dada (vector). La variable maxSum es una de las sumas máximas posibles. Una matriz tiene al menos una suma máxima. La variable runTotal representa el total acumulado en cada índice. Ambos se inicializan con el primer valor de la matriz. En este algoritmo, si el siguiente valor en la matriz es mayor que el total acumulado, ese siguiente valor se convertirá en el nuevo total acumulado.
Hay un bucle for principal. El escaneo comienza desde 1 y no desde cero debido a la inicialización de las variables, maxSum y runTotal a A[0], que es el primer elemento de la matriz dada.
En el bucle for, la primera declaración determina un total acumulado temporal al agregar el valor actual a la suma acumulada de todos los valores anteriores.
A continuación, hay una construcción if/else. Si el valor actual solo es mayor que el total acumulado hasta el momento, ese valor único se convierte en el total acumulado. Esto es útil especialmente si todos los valores en la matriz dada son negativos. En este caso, el valor negativo más alto solo se convertirá en el valor máximo (la respuesta). Si el valor actual por sí solo no es mayor que el total acumulado temporal hasta el momento, entonces el total acumulado se convierte en el total acumulado anterior más el valor actual, esta es la parte else de la construcción if/else.
El último segmento de código en el ciclo for elige entre cualquier suma máxima anterior para una secuencia anterior (sub-arreglo) y cualquier suma máxima actual para una secuencia actual. Por lo tanto, se elige el valor más alto. Puede haber más de una suma máxima de subarreglo. Tenga en cuenta que el total acumulado aumentaría y disminuiría, ya que la matriz se escanea de izquierda a derecha. Cae a medida que se encuentra con valores negativos.
La suma máxima final del subarreglo elegido se devuelve después del ciclo for.
El contenido de una función principal de C++ adecuada, para la función del algoritmo de Kadane es:
vector < En t > un = { 5 , - 7 , 3 , 5 , - 2 , 4 , - 1 } ; // { 3 , 5 , - 2 , 4 } - > 10int ret1 = maxSunArray ( A ) ;
cout << ret1 << fin;
vector < En t > B = { - 2 , 1 , - 3 , 4 , - 1 , 2 , 1 , - 5 , 4 } ; // { 4 , − 1 , 2 , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << fin;
vector < En t > C = { 3 , 2 , - 6 , 4 , 0 } ; // { 3 , 2 } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << fin;
vector < En t > re = { 3 , 2 , 6 , - 1 , 4 , 5 , - 1 , 2 } ; // { 3 , 2 , 6 , - 1 , 4 , 5 , - 1 , 2 } - > 5
int ret4 = maxSunArray ( D ) ;
cout << net4 << fin;
vector < En t > mi = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , 15 , 4 , - 8 , - 15 , - 22 } ; // { 6 , 5 , 10 , - 5 , 15 , 4 } - > 35
int ret5 = maxSunArray ( Y ) ;
cout << ret5 << fin;
vector < En t > F = { - 4 , 10 , 15 , 9 , - 5 , - 20 , - 3 , - 12 , - 3 , 4 , 6 , 3 , 2 , 8 , 3 , - 5 , - 2 } ; // { 10 , 15 , 9 } - > 34
int ret6 = maxSunArray ( F ) ;
cout << derecha 6 << fin;
Con eso, la salida será:
10
6
5
20
35
34
Cada respuesta de línea aquí corresponde a una matriz dada, en orden.
Conclusión
La complejidad temporal del algoritmo de Kadane es O(n), donde n es el número de elementos en el arreglo dado. Esta complejidad de tiempo es la más rápida para el problema de subarreglo máximo. Hay otros algoritmos que son más lentos. La idea del algoritmo de Kadane es hacer el total acumulado, mientras se comparan las sumas máximas a medida que se encuentran, moviéndose de izquierda a derecha en la matriz dada. Si el valor actual solo es mayor que el total acumulado hasta el momento, ese valor único se convierte en el nuevo total acumulado. De lo contrario, el nuevo total acumulado es el total acumulado anterior más el elemento actual, como se anticipó, a medida que se escanea la matriz dada.
Puede haber más de una suma máxima, para diferentes subarreglos posibles. Se elige la suma máxima más alta, para todos los sub-arreglos posibles.
¿Cuáles son los índices limitantes para el rango de la suma máxima elegida? – ¡Esa es discusión para otro momento!
cris