Maximise sum of "non-overlapping" numbers in square array - help with proof

A question was posted on Stack Overflow asking for an algorithm to solve this problem:


I have a matrix (call it A) which is nxn. I wish to select a subset
(call it B) of points from matrix A. The subset will consist of n
elements, where one and only one element is taken from each row and
from each column of A. The output should provide a solution (B) such
that the sum of the elements that make up B is the maximum possible
value, given these constraints (eg. 25 in the example below). If
multiple instances of B are found (ie. different solutions which give
the same maximum sum) the solution for B which has the largest minimum
element should be selected.


B could also be a selection matrix which is nxn, but where only the n
desired elements are non-zero.


For example: if A =

|5 4 3 2 1|
|4 3 2 1 5|
|3 2 1 5 4|
|2 1 5 4 3|
|1 5 4 3 2|

=> B would be

|5 5 5 5 5|

I proposed a dynamic programming solution which I suspect is as efficient as any solution is going to get. I've copy-pasted my proposed algorithm below.

• Let $A$ be a square array of $n$ by $n$ numbers.

• Let $A_{i,j}$ denote the element of $A$ in the ith row and jth column.

• Let $S( i_1:i_2, j_1:j_2 )$ denote the optimal sum of non-overlapping numbers for a square subarray of $A$ containing the intersection of rows $i_1$ to $i_2$ and columns $j_1$ to $j_2$.

Then the optimal sum of non-overlapping numbers is denoted S( 1:n , 1:n ) and is given as follows:

$$S( 1:n , 1:n ) = \max \left \{ \begin{array}{l} S( 2:n , 2:n ) + A_{1,1} \\
S( 2:n , 1:n-1 ) + A_{1,n} \\
S( 1:n-1 , 2:n ) + A_{n,1} \\
S( 1:n-1 , 1:n-1 ) + A_{n,n} \\
\end{array} \right.$$

Note that S( i:i, j:j ) is simply Aij.

That is, the optimal sum for a square array of size n can be determined by separately computing the optimal sum for each of the four

Actually, I don't believe your proposed solution is correct. An example where you might need this case

|   #    |
| #   # #|
| #   # #| 
| #   # #|

might be

| 1 2 1 1|
| 2 1 1 1|
| 1 1 1 2| 
| 1 1 2 1|

The optimal solution consists of all 2s, while there are only 1s in the corners; therefore, you cannot find an optimal solution just by starting at the corners.

StackExchange Computer Science Q#1597, answer score: 7