Camino de máxima suma en una matriz
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
1 2 3 |
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) |
moviéndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:
1 2 3 4 5 6 7 8 9 10 |
[1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,12,3,8,9] [1,6,11,3,4,9] [1,6,12,3,4,9] [1,7,12,3,4,9] [1,6,12,8,4,9] [1,7,12,8,4,9] [1,7, 3,8,4,9] |
La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.
Definir la función
1 |
caminoMaxSuma :: Matrix Int -> [Int] |
tal que caminoMaxSuma m
es un camino de máxima suma en la matriz m
desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,
1 2 3 4 |
λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) [1,7,12,8,4,9] λ> sum (caminoMaxSuma (fromList 500 500 [1..])) 187001249 |