Skip to content

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
19
20
class Solution {
 public:
  long long maxMatrixSum(vector<vector<int>>& matrix) {
    long absSum = 0;
    int minAbs = INT_MAX;
    // 0 := even number of negatives
    // 1 := odd number of negatives
    int oddNeg = 0;

    for (const vector<int>& 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
18
19
class Solution {
  public long maxMatrixSum(int[][] matrix) {
    long absSum = 0;
    int minAbs = Integer.MAX_VALUE;
    // 0 := even number of negatives
    // 1 := odd number of negatives
    int oddNeg = 0;

    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
15
16
class Solution:
  def maxMatrixSum(self, matrix: List[List[int]]) -> int:
    absSum = 0
    minAbs = math.inf
    # 0 := even number of negatives
    # 1 := odd number of negatives
    oddNeg = 0

    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