Kadane Algorithim

Kadane-algorithim

Esta es la solución de JavaScript para uno de los algoritim de famosos programación dinámica de Algo Kadane.

Declaración del problema

Dada una matriz a = {a1, a2, ..., un} de n elementos, encuentre la suma máxima posible de un

Subadray contigua no contigua (no necesariamente contigua) subarrray.
No se deben considerar los subarrays/subsecuencias vacías.

Este video de YouTube de Ben Wright podría ser útil para comprender el algoritmo Kadane para la subarrray máxima en una secuencia 1-D.

Formato de entrada

La primera línea de la entrada tiene un entero T. t casos que siguen. Cada caso de prueba comienza con un entero N. En la siguiente línea, N entegadores siguen representando los elementos de la matriz A.

Restricciones:

1≤t≤10
1≤n≤105
−104≤ai≤104

La subarrañas y las subsecuencias que considere deben tener al menos un elemento.

Formato de salida

Dos espacio separados, enteros que denotan la subarray máxima contigua y no contigua. Se debe seleccionar y colocar al menos un entero y colocar en los subarrañas (esto puede ser necesario en los casos en que todos los elementos son negativos).

Entrada de muestra

2
4
1 2 3 4
6
2-1 2 3 4 -5

Salida de muestra

10 10
10 11

Explicación

En el primer caso: la suma máxima para elementos contiguos y no contiguos es la suma de todos los elementos (ya que todos son positivos).

En el segundo caso: [2-1 2 3 4] -> Esto forma la sub -array contigua con la suma máxima. Para la suma máxima de un grupo de elementos no decisores no necesarios, simplemente agregue todos los elementos positivos.