как найти максимальную сумму L в матрице?

Question

Вот еще одна проблема динамического программирования, которая находит максимальную сумму L (шахматный конь - 4 предмета) в данной матрице (mxn)

Например:

1 2 3

4 5 6

7 8 9

L: (1,2,3,6), (1,4,5,6), (1,2,5,8), (4,5,6,9) ...

и самая большая сумма равна сумме (L) = сумма (7,8,9,6) = 30

чтоО (сложность) оптимального решения?

это выглядит так задача (подматрица с максимальной суммой)

1. Скажем, все предметыположительный

2. положительный и отрицательный

Любые идеи приветствуются!

Answer 1

Если ваш L имеет постоянный размер (как вы говорите, 4 элемента), просто вычислите его сумму по всем позициям