Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Given an **N*N** size matrix, you have to re-arrange the elements of the matrix in such a way that the difference between the summation of the elements of the main diagonal and the summation of the elements of the seconday diagonal is as large as possible. You can swap between any two elements of the matrix to re-arrange the matrix.

The main diagonal of a matrix consists of those elements that lie on the diagonal that runs from top left to bottom right. And the secondary diagonal of a matrix consists of those elements that lie on the diagonal that runs from top right to bottom left.

In the first line of input, there will be a number **N** **(3 ≤ N ≤ 100)** as described above. Then there will be **N** integers in each of the next **N** lines denoting the matrix. The elements of the matrix will lie in the range **[-106,106]**. In other words, the absolute value of each element of the matrix will not exceed **106**.

In a single line, print the maximum possible difference between the summation of the elements of the main diagonal and the summation of the elements of the secondary diagonal after re-arranging.

Input | Output |
---|---|

3 -11 5 8 2 6 17 4 -3 2 | 39 |

**Explanation of first test case:**

We can re-arrange the matrix to:

```
17 5 -11
2 6 4
-3 2 8
```

The difference is (17+6+8) - (-11+6-3) = 39, which is the maximum in this case.

89% Solution Ratio

ghazanfarEarliest,

Circle.21Fastest, 0.0s

oneoff.njpVi3LIlOLightest, 131 kB

touhidurrrShortest, 119B

Login to submit

If N is an odd number, the main diagonal and the secondary diagonal have an element in common (namel...

Toph uses cookies. By continuing you agree to our Cookie Policy.