月度归档： 2026 年 1 月

目标

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

• 选择 matrix 中 相邻 两个元素，并将它们都 乘以 -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

思路

有一个 n x n 矩阵，每次操作可以将相邻的元素乘以 -1，执行操作任意次，求能够得到的最大方阵和。

经过观察发现，可以将任意两个元素乘以 -1，只需对路径上的每个元素执行操作，改变 (cur, next) 的符号，中间每个元素的符号都被改变了两次，即首尾元素改变了符号。

只需判断矩阵中负数的个数，如果是偶数，可以将负数全部变为相反数；如果是奇数，则需要找到最小的非负数，将其变为负数，其余元素全部变为非负数。

代码

/**
 * @date 2026-01-05 9:07
 */
public class MaxMatrixSum1975 {

    public long maxMatrixSum(int[][] matrix) {
        long res = 0L;
        int negativeCnt = 0;
        int min = Integer.MAX_VALUE;
        for (int[] row : matrix) {
            for (int col : row) {
                res += Math.abs(col);
                min = Math.min(min, Math.abs(col));
                if (col < 0) {
                    negativeCnt++;
                }
            }
        }
        if (negativeCnt % 2 == 1) {
            res -= 2 * min;
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 0 。

示例 1：

输入：nums = [21,4,7]
输出：32
解释：
21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案仅为 21 的所有因数的和。

示例 2:

输入: nums = [21,21]
输出: 64

示例 3:

输入: nums = [1,2,3,4,5]
输出: 0

说明：

• 1 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^5

思路

有一个整数数组 nums，返回恰好有 4 个因数的元素的这些因数之和，如果不存在，返回 0。

首先数组元素至少有两个因数（1 和它本身），只需要再找到两个因数即可。从 2 ~ sqrt(num) 判断能否整除 num，如果可以加上 i 与 num / i，需要特殊处理 i * i = num 的情况，这时因数只能算一个。

代码

/**
 * @date 2026-01-04 9:05
 */
public class SumFourDivisors1390 {

    public int sumFourDivisors(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res += sum(num);
        }
        return res;
    }

    public int sum(int num) {
        int cnt = 2;
        int sum = num + 1;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                if (cnt == 4) {
                    sum = 0;
                    break;
                }
                if (i * i == num) {
                    sum += i;
                    cnt++;
                } else {
                    sum += i + num / i;
                    cnt += 2;
                }

            }
        }
        return cnt == 4 ? sum : 0;
    }

}

性能