Obtener máximo subsum de una matriz

Recientemente tuve esta pregunta en una prueba y no entiendo en absoluto lo que la pregunta está pidiendo, especialmente en base a los ejemplos:

max_subsum

Escriba un método, max_subsum (números), que toma una matriz y devuelve los índices de inicio y fin del rango consecutivo que tiene la sum más grande.

max_subsum ([100, -101, 200, -3, 1000]) == [2, 4]

max_subsum ([1, 2, 3]) == [0, 2]

Consejos: iterar a través de todos los subarrays; Calcule la sum de cada subarreglo y compárelo con el subsum máximo visto hasta ahora. Un subarray se define por sus índices de inicio y final, por lo que se itera a través de todos los pares de índices. Probablemente deberías usar dos bucles, uno nested dentro del otro.

No veo ningún subarrays en los ejemplos. El resultado de los ejemplos simplemente muestra los índices de los valores más pequeños y más grandes en la matriz. Si eso es lo que pregunta la pregunta, entonces qué sum de subarrays está sucediendo. Debo estar perdiendo algo simple, simplemente no sé qué es eso. ¿Alguien más lo ve?

Estos son los subarreglos de la primera matriz junto con sus sums:

 [100].inject(:+) #=> 100 [100, -101].inject(:+) #=> -1 [100, -101, 200].inject(:+) #=> 199 [100, -101, 200, -3].inject(:+) #=> 196 [100, -101, 200, -3, 1000].inject(:+) #=> 1196 [-101].inject(:+) #=> -101 [-101, 200].inject(:+) #=> 99 [-101, 200, -3].inject(:+) #=> 96 [-101, 200, -3, 1000].inject(:+) #=> 1096 [200, -3, 1000].inject(:+) #=> 1197 [-3, 1000].inject(:+) #=> 997 [1000].inject(:+) #=> 1000 

[200, -3, 1000] tiene la sum más grande

Aquí está mi solución rápida a su problema =)

Divide las llamadas para entender lo que estoy haciendo =)

 def max_subsum(a) (0...a.length).flat_map { |i| (i...a.length).map { |j| i..j } }.inject([a[0], 0..0]) { |max, i| a[i].inject(:+) > max.first ? [a[i].inject(:+),i ]: max }.last end 

Salida:

 max_subsum([100, -101, 200, -3, 1000]) => 2..4 max_subsum([1, 2, 3]) => 0..2 

Puedes convertir a array … No me molesté porque me gusta el rango =)

Una solución de progtwigción dinámica para este problema sería más eficiente, pero creo que se espera que proporcione algo similar a lo que hice durante un examen 🙂

Explicación:

 (0...a.length).flat_map { |i| (i...a.length).map { |j| i..j } } 

Vuelve a mí todas las posibles posiciones consecutivas en la matriz. Puedes considerar esto como tus bucles nesteds.

Luego estoy inyectando el valor [a[0], 0..0] y asumiendo que es la solución: a[0] es el valor máximo y 0..0 es el índice de principio a fin. Dentro de la inyección, estoy comparando el máximo con la sum de la porción actual de la matriz de flat_map, si es más grande, devuelvo la división y el máximo.

El algoritmo de Kadane es lo que quieres. En este blog puedes encontrar buenas referencias también.