{x}
blog image

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:

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.

 

Constraints:

  • n == matrix.length == matrix[i].length
  • 2 <= n <= 250
  • -105 <= matrix[i][j] <= 105

Solution Explanation: Maximum Matrix Sum

This problem asks us to find the maximum possible sum of elements in a matrix after applying a specific operation any number of times. The operation involves choosing two adjacent elements and multiplying both by -1. The key insight is that this operation doesn't change the absolute sum of the matrix. Instead, it lets us manipulate the signs of the elements.

Core Idea:

The strategy revolves around minimizing the number of negative elements. If we have an even number of negative elements, we can always pair them up and negate adjacent pairs, effectively turning them all positive. However, if we have an odd number of negatives, we'll be left with at least one negative element. To maximize the sum in this case, we want to negate the smallest negative element, making it positive.

Algorithm:

  1. Calculate the sum of absolute values: Iterate through the matrix, summing the absolute values of all elements. This represents the maximum possible sum if all elements were positive.

  2. Count negative elements: Simultaneously count the number of negative elements in the matrix.

  3. Even Negative Count: If the count of negative elements is even, the maximum sum is simply the sum of absolute values calculated in step 1.

  4. Odd Negative Count: If the count of negative elements is odd, we need to find the smallest absolute value among the negative elements. This is because negating this smallest negative element will minimize the reduction in the overall sum. Subtract twice this smallest absolute value from the sum of absolute values (because we're changing its sign).

Time and Space Complexity:

  • Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the matrix. This is because we iterate through the matrix once to calculate the sum of absolute values and count negative numbers.
  • Space Complexity: O(1). The algorithm uses only a few variables to store intermediate results; it doesn't use extra space proportional to the input size.

Code Implementation (Python):

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        min_abs = float('inf')  # Initialize with a large value
        total_abs_sum = 0
        neg_count = 0
 
        for row in matrix:
            for num in row:
                abs_num = abs(num)
                total_abs_sum += abs_num
                if num < 0:
                    neg_count += 1
                min_abs = min(min_abs, abs_num)
 
        if neg_count % 2 == 0:
            return total_abs_sum
        else:
            return total_abs_sum - 2 * min_abs

The code in other languages (Java, C++, Go, TypeScript, Rust, Javascript) follows the same logic, differing only in syntax. They all achieve the same time and space complexity.