Maximum Matrix Sum

Can you solve this real interview question? 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 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.

 

Example 1:

[https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex1.png]

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:

[https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex2.png]

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.

Solution

class Solution(object):
    def maxMatrixSum(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        min_value = float('inf')  # Equivalent to Integer.MAX_VALUE
        total_sum = 0
        neg_count = 0

        for row in matrix:
            for value in row:
                if value < 0:
                    neg_count += 1
                abs_value = abs(value)
                min_value = min(min_value, abs_value)
                total_sum += abs_value

        if neg_count % 2 == 0:
            return total_sum
        return total_sum - 2 * min_value