Maximum Matrix sum

Intuition

• Multiplying two adjacent elements by -1 effectively flips their signs.
• This operation can convert negative values into positive ones, which increases the total sum.
• If the total number of negative values in the matrix is even, we can flip all negatives into positives.
• If the total number of negative values is odd, one negative will remain after maximizing positive contributions.
• If one negative value must remain (odd negatives), it’s optimal to minimize its absolute value by keeping the smallest absolute value as negative.

Approach

• Count the total number of negative values.
• Compute the smallest absolute value in the matrix.
• Compute the sum of the absolute values of all elements in the matrix.

Complexity

• Time complexity: O(N²) where N is matrix length.

• Space complexity: O(1) with a few calculation for sum, min_abs and count_neg.

Code

```cpp [] class Solution { public: long long maxMatrixSum(vector>& matrix) { long long res = 0; int negativeCount = 0, minAbs = INT_MAX;

    for (auto& row: matrix) {
        for (auto& x: row) {
            res += abs(x);
            minAbs = min(minAbs, abs(x));
            negativeCount += (x < 0);
        }
    }

    if (negativeCount & 1) res -= minAbs * 2;
    return res;
}

}; rust [] impl Solution { pub fn max_matrix_sum(matrix: Vec>) -> i64 { let (mut sum, mut min_abs, mut count_neg) = (0i64, i32::MAX, 0); for row in matrix.iter() { for &val in row.iter() { if val < 0 { count_neg += 1; } min_abs = min_abs.min(val.abs()); sum += val.abs() as i64; } } if count_neg % 2 == 1 { sum -= (2 * min_abs) as i64; } sum } } ```

```go []

import "math" func maxMatrixSum(matrix [][]int) int64 { sum := int64(0) minValue, nNeg := math.MaxInt32, 0 for i := range matrix { for j := range matrix[i] { if matrix[i][j] < 0 { nNeg++ sum -= int64(matrix[i][j]) minValue = min(minValue, -matrix[i][j]) } else { sum += int64(matrix[i][j]) minValue = min(minValue, matrix[i][j]) } } } if nNeg % 2 == 1 { sum -= int64(2*minValue) }

return sum

} ```