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.
3 -11 5 8 2 6 17 4 -3 2
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.
Login to submit
If N is an odd number, the main diagonal and the secondary diagonal have an element in common (namel...