Problema de subraya máximo en C ++

El problema máximo de la sub-array es el mismo que el problema máximo de corte. Este tutorial discute el problema con la codificación en c++. La pregunta es: ¿Cuál es la suma máxima de cualquier posible secuencia 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 sub-array. 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 A = 5, -7, 3, 5, -2, 4, -1;

La porción (sub -array) con la suma máxima es la secuencia, 3, 5, -2, 4, que da una suma de 10. Ninguna otra secuencia posible, incluso toda la matriz, 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 B = -2, 1, -3, 4, -1, 2, 1, -5, 4;

La porción (sub-matra) 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 de la sub-matra por suma máxima.

Considere el siguiente vector:

vector C = 3, 2, -6, 4, 0;

La porción (sub-matra) con la suma máxima es la secuencia, 3, 2 que da una suma de 5.

Considere el siguiente vector:

vector D = 3, 2, 6, -1, 4, 5, -1, 2;

La sub -array con la suma máxima es la secuencia, 3, 2, 6, -1, 4, 5, -1, 2 que da una suma de 20. Es toda la matriz.

Considere el siguiente vector:

vector E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22;

Hay dos sub-matrices con sumas máximas, aquí. La suma más alta es la que se considera una solución (respuesta) para el problema de sub-matrices máximo. Las sub -matrices son: 5, 7 con una suma de 12 y 6, 5, 10, -5, 15, 4 con una suma de 35. Por supuesto, la porción con la suma de 35 es la respuesta.

Considere el siguiente vector:

vector F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2;

Hay dos sub-matrices con sumas máximas. La suma más alta es la que se considera la solución para el problema de sub-array. Las sub-matrices son: 10, 15, 9 con una suma de 34, y 4, 6, 3, 2, 8, 3 con una suma de 26. Por supuesto, la porción con la suma de 34 es la respuesta porque el problema es buscar la subarray con la suma más alta y no la subarray con la suma más alta.

Desarrollar el algoritmo de Kadane

La información en esta sección del tutorial no es el trabajo original de Kadane. Es la propia forma del autor de enseñar el algoritmo de Kadane. Uno de los vectores anteriores, con sus totales, está en esta tabla:

Ejecutar el total de un índice es la suma de todos los valores anteriores, incluido el para el índice. Hay dos secuencias con sumas máximas aquí. Son 5, 7, lo que da una suma de 12, y 6, 5, 10, -5, 15, 4, lo que da una suma de 35. La secuencia que da una suma de 35 es lo que se desea.

Observe que para los totales de carrera, 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 de la carrera mientras se compara 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 de carrera, 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 de carrera, hay dos picos que son los valores, 30 y 13. Estos picos corresponden a los últimos índices de las dos secuencias.

Una vez más, la idea del algoritmo de Kadane es hacer el total de funcionamiento mientras se compara las sumas máximas a medida que se encuentran, moviéndose de izquierda a derecha en la matriz dada.

Código del algoritmo de Kadane en C++

El código dado en esta sección del artículo no es necesariamente lo que Kadane usó. Sin embargo, es por su algoritmo. El programa como muchos otros programas C ++ comenzaría con:

#incluir
#incluir

usando el espacio de nombres STD;

Hay inclusión de 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 de funcionamiento al comparar 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 &A)
int n = a.tamaño();
int maxsum = a [0];
int runTotal = a [0];
para (int i = 1; i < N; i++)
int tempruntotal = runTotal + a [i]; // podría ser más pequeño que un [i]
if (a [i]> tempuntotal)
runTotal = a [i]; // en caso de que un [i] sea más grande que correr en total
demás
runTotal = TEMPRUNTOTAL;
if (runTotal> maxsum) // Comparando todas las sumas máximas
maxsum = runTotal;

devolver maxsum;

El tamaño, n de la matriz dada (vector) está determinado. 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 de ejecución 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 de ejecución, entonces ese valor siguiente se convertirá en el nuevo total de running.

Hay un bucle principal. El escaneo comienza desde 1 y no cero debido a la inicialización de las variables, maxsum y runtotal a un [0] que el primer elemento de la matriz dada.

En el bucle for-loop, la primera declaración determina un total de ejecución 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 por sí solo es mayor que el total de ejecución hasta ahora, entonces ese valor único se convierte en el total de ejecución. 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 de ejecución temporal hasta ahora, entonces el total de ejecución se convierte en el total de ejecución anterior más el valor actual, esto es el otro de la construcción if/else.

El último segmento de código en el bucle for-loop elige entre cualquier suma máxima anterior para una secuencia anterior (sub-array) y cualquier suma máxima actual para una secuencia de corriente. Por lo tanto, el valor más alto se elige. Puede haber más de una suma de sub-array máxima. Tenga en cuenta que el total de la carrera se elevaría y caería, ya que la matriz se escanea de izquierda a derecha. Cae a medida que cumple con los valores negativos.

La suma de la sub-array máxima elegida final se devuelve después del bucle for-bucle.

El contenido para una función principal de C ++ adecuada, para la función de algoritmo de Kadane es:

vector A = 5, -7, 3, 5, -2, 4, -1; // 3, 5, -2, 4 -> 10
int ret1 = maxsunArray (a);
cout << ret1 << endl;
vector B = -2, 1, -3, 4, -1, 2, 1, -5, 4; // 4, −1, 2, 1 -> 6
int ret2 = maxsunArray (b);
cout << ret2 << endl;
vector C = 3, 2, -6, 4, 0; // 3, 2 -> 5
int ret3 = maxSunArray (c);
cout << ret3 << endl;
vector D = 3, 2, 6, -1, 4, 5, -1, 2; // 3, 2, 6, -1, 4, 5, -1, 2 -> 5
int ret4 = maxSunArray (d);
cout << ret4 << endl;
vector E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22; // 6, 5, 10, -5, 15, 4 -> 35
int ret5 = maxsunArray (e);
cout << ret5 << endl;
vector 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 << ret6 << endl;

Con eso, la salida será:

10

6

5

20

35

34

Cada respuesta de línea aquí corresponde a una matriz determinada, en orden.

Conclusión

La complejidad del tiempo para el algoritmo de Kadane es O (n), donde n es el número de elementos en la matriz dada. Este tiempo, la complejidad es la más rápida para el problema máximo de sub-array. Hay otros algoritmos que son más lentos. La idea del algoritmo de Kadane es hacer el total de la carrera, mientras se compara las sumas máximas a medida que se encuentran, moviéndose de izquierda a derecha en la matriz dada. Si el valor actual por sí solo es mayor que el total de ejecución hasta ahora, entonces ese valor único se convierte en el nuevo total de ejecución. De lo contrario, el nuevo total de ejecución es el total de ejecución anterior más el elemento actual, como se anticipó, ya que se escanea la matriz dada.

Puede haber más de una suma máxima, para diferentes posibles sub-matrices. Se elige la suma máxima más alta, para todas las sub-matrices posibles,.

¿Cuáles son los índices limitantes para el rango de la suma máxima elegida?? - Eso es discusión por otro tiempo!

Chrys