how to find the maximum L sum in a matrix?

Question

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

For example :

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) ...

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

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

it looks like this problem (submatrix with maximum sum)

Say all items are positive
Both positive and negative

Any ideas are welcome!

Where did you come across this problem? It might be helpful if you provide some context. — MAK, Dec 21 '10 at 08:34
@MAK it comes to my mind :) I have also hard version of it. I'm working on and will post in a few days. I don't know maybe there is a problem like that on the web — , Dec 21 '10 at 08:43

score 5 · Accepted Answer · answered Dec 21 '10 at 16:56

5

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.

answered Dec 21 '10 at 16:56

Keith Randall

22,985
2
35
54

Omega(nm) is a trivial lower bound, you need to look at every element in the array. – Keith Randall Dec 21 '10 at 17:38
This is correct for the problem as stated. If the L is constant size it is a trivial problem. – Chris Hopman Dec 22 '10 at 09:41
3

@hilal: Sometimes brute force is the only answer, in which case it's the right answer :) – j_random_hacker Dec 22 '10 at 10:20

how to find the maximum L sum in a matrix?

1 Answers1

Linked