[Solved]: Maximise sum of "non-overlapping" numbers in square array - help with proof

Problem Detail: 

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?

Asked By : Li-aung Yip

Answered By : jpalecek

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1597