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 matrix and 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.

&nbsp;
Example 1:

Input: matrix = [[1,-1],[-1,1]]
Output: 4
Explanation: We can follow the following steps to reach sum equals 4:
- Multiply the 2 elements in the first row by -1.
- Multiply the 2 elements in the first column by -1.


Example 2:

Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
Output: 16
Explanation: We can follow the following step to reach sum equals 16:
- Multiply the 2 last elements in the second row by -1.


&nbsp;
Constraints:


	n == matrix.length == matrix[i].length
	2 &lt;= n &lt;= 250
	-105 &lt;= matrix[i][j] &lt;= 105


class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        # count -'s
        count = 0
        for row in matrix:
            for col_num in row:
                if col_num < 0:
                    count += 1
        tot_sum = sum([sum([abs(x) for x in row])
                       for row in matrix])
        if count % 2 == 0:
            return tot_sum
        else:
            min_val = min([min([abs(x) for x in row])
                       for row in matrix])
            return tot_sum - 2 * min_val
class Solution {
    public long maxMatrixSum(int[][] matrix) {
        long ans = 0;
        int neg = 0;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] < 0) {
                    neg++;
                }
                ans += Math.abs(matrix[i][j]);
                if(min > Math.abs(matrix[i][j]))
                	min = Math.abs(matrix[i][j]);
            }
        }
        if(neg % 2 == 0)
        	return ans;
        else
        	return ans - 2*min;
    }
}
/**
 * @author      : archit
 * @GitHub      : archit-1997
 * @Email       : architsingh456@gmail.com
 * @file        : maximumMatrixSum.cpp
 * @created     : Saturday Aug 21, 2021 20:11:56 IST
 */

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        int r=matrix.size(),c=matrix[0].size();

        //we need to find the min number in the matrix and also count of negative numbers in the matrix
        int small=INT_MAX,count=0;
        long long int sum=0;

        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                int val=matrix[i][j];
				//finding the smallest absolute value in the matrix
                small=min(small,abs(val));
				//counting the negative numbers
                if(val<0)
                    count++;
				//finding the sum of all the values
                sum+=abs(val);
            }
        }
		//if even number of negatives, then just return sum
        if(count%2==0)
            return sum;
        else
		//subtract the value of the min absolute element
            return sum-2*small;
    }
};
var maxMatrixSum = function(matrix) {
    const MAX= Number.MAX_SAFE_INTEGER;

    const m = matrix.length;
    const n = matrix[0].length;

    let negs = 0;

    let totAbsSum = 0;
    let minAbsNum = MAX;

    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            if (matrix[i][j] < 0) ++negs;

            totAbsSum += Math.abs(matrix[i][j]);
            minAbsNum = Math.min(minAbsNum, Math.abs(matrix[i][j]));
        }
    }

    if (negs % 2 === 1) totAbsSum -= (2 * minAbsNum);

    return totAbsSum;
};
Maximum Matrix Sum