如何在矩阵中找到最大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)......

最大的和是sum(L)= sum(7,8,9,6)= 30

什么是最优解的O(复杂性)？

它看起来像这个问题(具有最大总和的子矩阵)

1. 说所有项目都是积极的

2. 积极和消极

欢迎任何想法!

Answer 1

如果你的L是恒定大小(正如你所说的那样是4个元素),只需计算所有<n*m个位置的总和并找到最大值.重复8种不同的方向.这总体上是O(nm).