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 sub-arrays of size n-1, and then maximising the sum of the sub-array and the element that was "left out".

S for |# # # #|
      |# # # #|
      |# # # #|
      |# # # #|

Is the best of the sums S for:

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




This is a very elegant algorithm and I strongly suspect that it is correct, but I can't come up with a way to prove it is correct.

The main difficulty I am having it proving that the problem displays optimal substructure. I believe that if the four potential choices in each calculation are the only four choices, then this is enough to show optimal substructure. That is, I need to prove that this:

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


Is not a valid solution, either because it's impossible (i.e. proof by contradiction) or because this possibility is already accounted for by one of the four "n-1 square" variations.

Can anyone point out any flaws in my algorithm, or provide a proof that it really does work?
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.