Maximum matrix sum

Array Greedy Matrix

67.6% acceptance

Feb 25, 2026

1616

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_matrix_sum(matrix: Vec<Vec<i32>>) -> i64 {
    let mut total_abs: i64 = 0;
    let mut min_abs = i64::MAX;
    let mut neg_count = 0;
    
    for row in &matrix {
      for &val in row {
        let abs_val = (val as i64).abs();
        total_abs += abs_val;
        min_abs = min_abs.min(abs_val);
        if val < 0 {
          neg_count += 1;
        }
      }
    }
    
    // If odd number of negatives, we must keep one negative (the smallest absolute value)
    if neg_count % 2 == 1 {
      total_abs - 2 * min_abs
    } else {
      total_abs
    }
  }
}