我是伟大的矩阵

1975 年。最大矩阵和

难度：中等

主题：数组、贪婪、矩阵

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

• 选择矩阵中任意两个相邻元素，并将每个元素乘以-1。

两个元素被视为相邻当且仅当它们共享边框。

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

示例1：

• 输入： 矩阵 = [[1,-1],[-1,1]]
• 输出： 4
• 解释：我们可以按照以下步骤使总和等于 4：
  • 将第一行中的 2 个元素乘以 -1。
  • 将第一列中的 2 个元素乘以 -1。

示例2：

• 输入： 矩阵 = [[1,2,3],[-1,-2,-3],[1,2,3]]
• 输出： 16
• 解释：我们可以按照以下步骤使总和等于 16：
  • 将第二行的最后 2 个元素乘以 -1。

约束：

• n == 矩阵.length == 矩阵[i].length
• 2
• -10⁵ 5

提示：

1. 尝试使用运算使每一行只有一个负数。
2. 如果只有一个负元素，则无法将其转换为正元素。

解决方案：

为了使用该运算最大化矩阵的总和，我们需要最小化总和的负贡献的绝对值。计划如下：

1. 计算负数：跟踪矩阵中存在多少个负数。
2. 查找最小绝对值：确定矩阵中的最小绝对值，如果负数为奇数，这将有帮助。
3. 调整奇数负数：如果负数的数量是奇数，则最小绝对值无法翻转为正数，这限制了最大可能的总和。

让我们用 PHP 实现这个解决方案：1975。最大矩阵和

<?php
/**
 * @param Integer[][] $matrix
 * @return Integer
 */
function maximumMatrixSum($matrix) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test case 1
$matrix1 = [[1, -1], [-1, 1]];
echo "Output: " . maximumMatrixSum($matrix1) . "\n"; // Output: 4

// Test case 2
$matrix2 = [[1, 2, 3], [-1, -2, -3], [1, 2, 3]];
echo "Output: " . maximumMatrixSum($matrix2) . "\n"; // Output: 16
?>

解释：

1. 绝对值求和： 计算所有元素的绝对值之和，因为最佳配置将尽可能多的负数翻转为正数。
2. 跟踪最小绝对值：当负数计数为奇数时，使用此功能调整总和。
3. 处理奇负数：当负数无法完全抵消时，从总和中减去最小绝对值的两倍，以考虑不可避免的负数。

复杂

• 时间复杂度： O(n^2)，因为矩阵被遍历一次。
• 空间复杂度： O(1)，因为除了变量之外没有使用额外的空间。

该解决方案在给定的限制内有效地工作。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是我是伟大的矩阵的详细内容。更多信息请关注PHP中文网其他相关文章！