1975. Maximum Matrix Sum

[mah-shamim]

Topics: Array, Greedy, Matrix

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

Hint:

1. Try to use the operation so that each row has only one negative number.
2. If you have only one negative element you cannot convert it to positive.

[mah-shamim]

We need to minimize the absolute value of the negative contributions to the sum. Here's the plan:

1. Count Negative Numbers: Track how many negative numbers are present in the matrix.
2. Find Minimum Absolute Value: Determine the smallest absolute value in the matrix, which will help if the number of negatives is odd.
3. Adjust for Odd Negatives: If the count of negative numbers is odd, the smallest absolute value cannot be flipped to positive, and this limits the maximum possible sum.

Let's implement this solution in PHP: 1975. Maximum Matrix Sum

<?php
/**
 * @param Integer[][] $matrix
 * @return Integer
 */
function maximumMatrixSum($matrix) {
    $n = count($matrix);
    $sum = 0;
    $minAbs = PHP_INT_MAX;
    $negativeCount = 0;

    // Iterate through the matrix
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n; $j++) {
            $sum += abs($matrix[$i][$j]);
            $minAbs = min($minAbs, abs($matrix[$i][$j]));
            if ($matrix[$i][$j] < 0) {
                $negativeCount++;
            }
        }
    }

    // If there is an odd number of negatives, subtract twice the smallest absolute value
    if ($negativeCount % 2 != 0) {
        $sum -= 2 * $minAbs;
    }

    return $sum;
}

// Test case 1
$matrix1 = [[1, -1], [-1, 1]];
echo "Output: " . maximumMatrixSum($matrix1) . "\n"; // Output: 4

// Test case 2
$matrix2 = [[1, 2, 3], [-1, -2, -3], [1, 2, 3]];
echo "Output: " . maximumMatrixSum($matrix2) . "\n"; // Output: 16
?>

Explanation:

1. Summation of Absolute Values: Compute the sum of absolute values of all elements since the optimal configuration flips as many negative numbers to positive as possible.
2. Track Smallest Absolute Value: Use this to adjust the sum when the count of negative numbers is odd.
3. Handle Odd Negatives: Subtract twice the smallest absolute value from the sum to account for the unavoidable negative element when the negatives cannot be fully neutralized.

Complexity

• Time Complexity: O(n^2), as the matrix is traversed once.
• Space Complexity: O(1), since no additional space is used apart from variables.

This solution works efficiently within the given constraints.

[kovatz]

Thanks for solving the "Maximum Matrix Sum" problem efficiently

[mah-shamim]

Thanks