1975. Maximum square matrix sum

This is the 23rd day of my participation in the August More Text Challenge.More challenges in August

I give you a matrix of n x n integers. You can perform the following operations any time:

Select two adjacent elements in the matrix and multiply them both by -1. Two elements are adjacent if they have common edges.

Your goal is to maximize the sum of the square matrix elements. Return the maximum sum of squares after you perform the above operations.

Example 1:

Input: matrix = [[1,-1],[-1,1]] Output: 4 Explanation: We can do the following to make and equal to 4:

Let’s multiply the first two entries in the first row by negative 1.
Let’s multiply the two entries in the first column times negative 1.
Example 2:

Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3] output: 16 Explanation: We can do the following to make and equal to 16:

Multiply the last two elements of the second row by negative 1.

Tip:

n == matrix.length == matrix[i].length
2 <= n <= 250

Their thinking

Two negative numbers can cancel out anywhere to make two positive numbers

As shown, take a portion of a two-dimensional array

We need to cancel out -1 and -9. We can do this by taking the negative of the underlined numbers, as shown above, to make two negative numbers in any position positive, leaving the rest unaffected

If the negative numbers are even, just enough to cancel each other out, the result is the absolute value of all the elements
If we have an odd number of negative numbers, it means we can’t cancel them out completely, and we’re going to end up with a negative number, and we’re going to have to pick a negative number that has the smallest absolute value, so that we have the smallest reduction

code

class Solution {
    public long maxMatrixSum(int[][] matrix) {

        long res=0,cnt=0,min=Integer.MAX_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                res+= Math.abs(matrix[i][j]);
                min=Math.min(min,Math.abs(matrix[i][j]));
                if (matrix[i][j]<0) { cnt++; }}}if (cnt%2= =1)
        {
                res-=2*min;
        }
        returnres; }}Copy the code

1975. Maximum square matrix sum