What is the maximum sum of squares of two non-attacking rooks placed on a matrix?

Question

There is a m x n matrix given each with integer elements. The problem says that we have to place two rooks on that matrix, such that they don't attack each other and the sum of the elements on which the rooks are placed is maximum.

Example: Let's say matrix is

2 5
1 3

Then non-attacking rooks can be placed only on 2,3 or 1,5 element positions. But the maximum sum is found in case of 1,5, so the function should return 1 + 5 = 6.

I thought that we could go through all the pairs of the array one by one and then return the maximum sum that we found, but I can't seem to find a better or efficient approach for this. My solution would be O(m * m * n * n) in terms of complexity.

What would be a better approach? I would appreciate any help.

Answer 1

1. For each row, find the top 2 values and remember the column where they were found. O(mn)

2. For each column, find the top 2 values and remember the row where they were found. O(mn)

3. The the remaining operations, we only use the two lists built above. We will not look at the matrix again:

   1. For each row, pretend to place a rook in that row and in the column with the highest value. For each column, sum that top value with the top value for the column, except for the column where the rook is, where we sum with the second highest value. Remember the row of the pretend rook and the column with the highest sum. O(mn)

   2. Repeat, but use the second highest value. O(mn)

Operation complete. O(mn) + O(mn) + O(mn) + O(mn) = O(mn)