Maximum Matrix Sum
You are given an n x n integer matrix. You can do the following operation any number of times:
- Choose any two adjacent elements of
matrixand multiply each of them by-1.
Two elements are considered adjacent if and only if they share a border.
Your goal is to maximize the summation of the matrix's elements. Return the maximum sum of the matrix's elements using the operation mentioned above.
Example 1
1 -1 -1 1
Input
matrix = [[1,-1],[-1,1]]Output
4By multiplying the two elements in the first row by
-1 and then the two elements in the first column by -1, all elements become positive and the sum is 4.Example 2
1 2 3 -1 -2 -3 1 2 3
Input
matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]Output
16Multiplying the two last elements in the second row by
-1 produces the maximum possible sum of 16.Constraints
- n == matrix.length == matrix[i].length
- 2 <= n <= 250
- -10^5 <= matrix[i][j] <= 10^5