# 1975. Maximum Matrix Sum

• Time: $O(n^2)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public: long long maxMatrixSum(vector>& matrix) { long long absSum = 0; int minAbs = INT_MAX; int oddNeg = 0; // 0 := even neg, 1 := odd neg for (const vector& row : matrix) for (const int num : row) { absSum += abs(num); minAbs = min(minAbs, abs(num)); if (num < 0) oddNeg ^= 1; } return absSum - oddNeg * minAbs * 2; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public long maxMatrixSum(int[][] matrix) { long absSum = 0; int minAbs = Integer.MAX_VALUE; int oddNeg = 0; // 0 := even neg, 1 := odd neg for (int[] row : matrix) for (final int num : row) { absSum += Math.abs(num); minAbs = Math.min(minAbs, Math.abs(num)); if (num < 0) oddNeg ^= 1; } return absSum - oddNeg * minAbs * 2; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution: def maxMatrixSum(self, matrix: List[List[int]]) -> int: absSum = 0 minAbs = math.inf oddNeg = 0 # 0 := even neg, 1 := odd neg for row in matrix: for num in row: absSum += abs(num) minAbs = min(minAbs, abs(num)) if num < 0: oddNeg ^= 1 return absSum - oddNeg * minAbs * 2