如何找到以矩阵的最大大号总和？

本文介绍了如何找到以矩阵的最大大号总和？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

下面是另一个动态规划的问题，找出最大L（国际象棋的马 - 4项）给定矩阵之和（MXN）

here is another dynamic programming problem that find the maximum L(chess horse - 4 item) sum in the given matrix (m x n)

例如：

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 : (1,2,3,6), (1,4,5,6), (1,2,5,8), (4,5,6,9) ...

和最大的总和是总和（L）=总和（7,8,9,6）= 30

and the biggest sum is sum(L) = sum(7,8,9,6) = 30

什么是最优解的O（复杂性）？

what is the O(complexity) of the optimal solution ?

它看起来像这样问题（子矩阵最大总和）

说的所有项目都是正

Say all items are positive

正反两方面

任何想法，欢迎！

推荐答案

如果你的L是固定的大小（4个元素，像你说的），只计算其总和所有＆LT; N * M的位置，找到最大的之一。重复8个不同的方向，你可以有。这是O（nm）的整体。

If your L is constant size (4 elements, as you say), just compute its sum over all < n*m positions and find the maximum one. Repeat for the 8 different orientations you could have. That's O(nm) overall.