Medium

题目描述

给你一个 n x n 的整数矩阵。你可以执行以下操作任意次数：

选择矩阵中任意两个相邻的元素，将它们都乘以 -1。

当且仅当两个元素共享一条边时，它们才被认为是相邻的。

你的目标是最大化矩阵元素的和。使用上述操作，返回矩阵元素的最大和。

示例 1:

输入: matrix = [[1,-1],[-1,1]]
输出: 4
解释: 我们可以按照以下步骤达到和为 4：
- 将第一行的 2 个元素乘以 -1。
- 将第一列的 2 个元素乘以 -1。

示例 2:

输入: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
输出: 16
解释: 我们可以按照以下步骤达到和为 16：
- 将第二行的最后 2 个元素乘以 -1。

约束条件:

  • n == matrix.length == matrix[i].length
  • 2 <= n <= 250
  • -10^5 <= matrix[i][j] <= 10^5

提示:

  • 尝试使用操作让每行只有一个负数。
  • 如果你只有一个负数元素，你无法将其转换为正数。

解题思路

这道题的关键洞察是理解操作的本质：每次操作会翻转两个相邻元素的符号。

首先分析操作的性质：

  1. 每次操作改变两个相邻元素的符号
  2. 这意味着负数的总个数的奇偶性保持不变

通过数学分析可以发现：

  • 如果矩阵中负数个数为偶数，我们可以通过一系列操作将所有数都变成正数
  • 如果矩阵中负数个数为奇数，我们最多只能让一个数保持负数

证明思路：可以把矩阵看作图，每个位置是节点，相邻位置有边。每次操作相当于翻转一条边连接的两个节点的符号。通过图论知识，我们可以证明连通图中任何两个节点的符号可以通过操作变得相同或相反，具体取决于它们之间路径长度的奇偶性。

基于以上分析，贪心策略是：

  1. 计算所有元素绝对值的和
  2. 统计负数的个数
  3. 如果负数个数为奇数，需要减去绝对值最小的元素的两倍（因为它必须保持负数）

代码实现

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        long long sum = 0;
        int negativeCount = 0;
        int minAbs = INT_MAX;
        
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum += abs(matrix[i][j]);
                if (matrix[i][j] < 0) {
                    negativeCount++;
                }
                minAbs = min(minAbs, abs(matrix[i][j]));
            }
        }
        
        if (negativeCount % 2 == 1) {
            sum -= 2 * minAbs;
        }
        
        return sum;
    }
};

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        total_sum = 0
        negative_count = 0
        min_abs = float('inf')
        
        for row in matrix:
            for val in row:
                total_sum += abs(val)
                if val < 0:
                    negative_count += 1
                min_abs = min(min_abs, abs(val))
        
        if negative_count % 2 == 1:
            total_sum -= 2 * min_abs
        
        return total_sum

public class Solution {
    public long MaxMatrixSum(int[][] matrix) {
        long sum = 0;
        int negativeCount = 0;
        int minAbs = int.MaxValue;
        
        int n = matrix.Length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum += Math.Abs(matrix[i][j]);
                if (matrix[i][j] < 0) {
                    negativeCount++;
                }
                minAbs = Math.Min(minAbs, Math.Abs(matrix[i][j]));
            }
        }
        
        if (negativeCount % 2 == 1) {
            sum -= 2 * minAbs;
        }
        
        return sum;
    }
}

var maxMatrixSum = function(matrix) {
    let negativeCount = 0;
    let minAbsValue = Infinity;
    let totalAbsSum = 0;
    
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[i].length; j++) {
            const val = matrix[i][j];
            const absVal = Math.abs(val);
            
            if (val < 0) negativeCount++;
            minAbsValue = Math.min(minAbsValue, absVal);
            totalAbsSum += absVal;
        }
    }
    
    return negativeCount % 2 === 0 ? totalAbsSum : totalAbsSum - 2 * minAbsValue;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n²)
空间复杂度O(1)

时间复杂度：需要遍历整个 n×n 矩阵一次来计算总和、负数个数和最小绝对值。 空间复杂度：只使用了常数个额外变量。