We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Matrix Sum

Number: 2089

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given an n x n integer matrix, you can perform an operation any number of times where you choose any two adjacent elements (sharing a border) and multiply each by -1. The goal is to maximize the sum of all elements in the matrix. Compute the maximum possible sum after performing the operations optimally.

Key Insights

  • Flipping the sign of two adjacent numbers does not affect the overall parity (even/odd nature) of the count of negative numbers.
  • You can effectively change the signs in pairs, which means if the total count of negative numbers is even, you can transform all values to positive.
  • If the count of negative numbers is odd, one number will remain negative, so you want that to be the smallest (by absolute value) to minimize the reduction in the maximum sum.
  • The answer thus becomes the sum of the absolute values of all elements, adjusted by subtracting twice the smallest absolute value if an odd number of negatives exists.

Space and Time Complexity

Time Complexity: O(n^2) – We traverse every element in the matrix once. Space Complexity: O(1) – Only constant extra space is needed (aside from input storage).

Solution

The approach leverages a greedy strategy:

  1. Iterate through the matrix and compute the sum of the absolute values of each element.
  2. Count the number of negative numbers and track the smallest absolute value.
  3. If the count of negatives is even, all negatives can be flipped to positive, so the maximum sum is the sum of absolute values.
  4. If the count of negatives is odd, one number will remain negative after optimal operations. To maximize the sum, choose the smallest absolute value to be negative. Therefore, subtract twice this minimum value from the total sum of absolute values.
  5. Use simple loops and arithmetic to achieve the solution.

Code Solutions

# Python solution for Maximum Matrix Sum

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        total_sum = 0            # Sum of absolute values of all elements
        min_abs_value = float('inf')  # Minimum absolute value in the matrix
        negative_count = 0       # Counter for negative numbers
        
        # Traverse through the matrix
        for row in matrix:
            for value in row:
                abs_value = abs(value)
                total_sum += abs_value    # Add the absolute value to total_sum
                min_abs_value = min(min_abs_value, abs_value)  # Update minimum absolute value
                if value < 0:
                    negative_count += 1  # Count negatives
        
        # If the number of negatives is odd, subtract twice the smallest absolute value
        if negative_count % 2 != 0:
            total_sum -= 2 * min_abs_value
        
        return total_sum
← Back to All Questions