Maximum Matrix Sum

In one operation, select two cells of the square matrix that share an edge and multiply both entries by -1. Diagonal neighbors do not share an edge. Perform any number of operations, including none, and return the largest possible sum of all entries.

Example 1:

Input: matrix = [[-1,-2],[3,4]]

Output: 10

Explanation: Flip the two adjacent entries in the first row. All entries then become positive, giving 1 + 2 + 3 + 4 = 10.

Example 2:

Input: matrix = [[-1,2],[3,4]]

Output: 8

Explanation: Each operation changes two signs. With no zero available, at least one negative entry must remain. Keeping -1 gives the maximum sum, -1 + 2 + 3 + 4 = 8.

Example 3:

Input: matrix = [[-2,0],[3,4]]

Output: 9

Explanation: Flip the two entries in the first row. The -2 becomes 2 and the zero stays zero, giving a total of 9.

Constraints:

• 2 <= matrix.length <= 250
• Every row has matrix.length entries.
• -100000 <= matrix[i][j] <= 100000