maximum-matrix-sum

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an <code>n x n</code> integer <code>matrix</code>. You can do the following operation any number of times:

<ul>
	<li>Choose any two adjacent elements of <code>matrix</code> and multiply each of them by <code>-1</code>.</li>
</ul>

Two elements are considered adjacent if and only if they share a border.

Your goal is to maximize the summation of the matrix&#39;s elements. Return the maximum sum of the matrix&#39;s elements using the operation mentioned above.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex1.png" style="width: 401px; height: 81px;" />
<pre>
Input: matrix = [[1,-1],[-1,1]]
Output: 4
Explanation: We can follow the following steps to reach sum equals 4:
- Multiply the 2 elements in the first row by -1.
- Multiply the 2 elements in the first column by -1.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex2.png" style="width: 321px; height: 121px;" />
<pre>
Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
Output: 16
Explanation: We can follow the following step to reach sum equals 16:
- Multiply the 2 last elements in the second row by -1.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == matrix.length == matrix[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 250</code></li>
	<li><code>-105 &lt;= matrix[i][j] &lt;= 105</code></li>
</ul>

maxMatrixSum

Maximum Matrix Sum

Greedy

Array

Matrix

给你一个&nbsp;<code>n x n</code>&nbsp;的整数方阵&nbsp;<code>matrix</code>&nbsp;。你可以执行以下操作&nbsp;任意次&nbsp;：

<ul>
	<li>选择&nbsp;<code>matrix</code>&nbsp;中&nbsp;相邻&nbsp;两个元素，并将它们都 乘以&nbsp;<code>-1</code>&nbsp;。</li>
</ul>

如果两个元素有 公共边&nbsp;，那么它们就是 相邻&nbsp;的。

你的目的是 最大化&nbsp;方阵元素的和。请你在执行以上操作之后，返回方阵的&nbsp;最大&nbsp;和。

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex1.png" style="width: 401px; height: 81px;">
<pre>输入：matrix = [[1,-1],[-1,1]]
输出：4
解释：我们可以执行以下操作使和等于 4 ：
- 将第一行的 2 个元素乘以 -1 。
- 将第一列的 2 个元素乘以 -1 。
</pre>

示例&nbsp;2：
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex2.png" style="width: 321px; height: 121px;">
<pre>输入：matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
输出：16
解释：我们可以执行以下操作使和等于 16 ：
- 将第二行的最后 2 个元素乘以 -1 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == matrix.length == matrix[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 250</code></li>
	<li><code>-105 &lt;= matrix[i][j] &lt;= 105</code></li>
</ul>