1. 问题描述：
给定一个 n × m 的整数矩阵，其中第 i 行第 j 列的元素为 aij。你可以进行任意多次如下操作：选择矩阵中的两个相邻元素，将它们均乘以 ?1。同一个元素可以被选中多次。你需要通过上述操作，使得矩阵中所有元素的和尽可能大。计算并输出这个和的最大可能值。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。每组数据第一行包含两个整数 n，m。接下来 n 行，每行包含 m 个整数，表示整个矩阵，其中第 i 行第 j 列的数为 aij。
【3763 数字矩阵（思维题）】输出格式
每组数据输出一行结果，表示矩阵的所有元素的最大可能和。
数据范围
1 ≤ T ≤ 100,
2 ≤ n，m ≤ 10，
?100 ≤ aij ≤ 100
输入样例：
2
2 2
-1 1
1 1
3 4
0 -1 -2 -3
-1 -2 -3 -4
-2 -3 -4 -5
输出样例：
2
30
来源：https://www.acwing.com/problem/content/description/3766/
2. 思路分析：
这道题目类似于3762题，我们也是需要挖掘一下题目的一些性质，可以发现对于矩阵中任意两个位置的数字我们都可以通过一条路径使得路径端点处的数字变为相反数，路径中的其余点是不变的（只有端点处乘了一次-1所以变为相反数），所以要想使得最终矩阵中的和最大我们需要尽可能使得负数变为正数，所以每一次我们可以选择两个负数将其变为正数，当负数的个数为偶数个的时候我们可以通过两两配对这样最终所有的负数都会变为正数，当负数的个数为奇数个的时候那么最终一定会剩下一个负数这个时候最终留下来的负数应该是绝对值最小的那个负数这样总和才可以最大，当我们发现这个性质之后问题就变得比较好处理了。
文章图片
3. 代码如下：
class Solution:
def process(self):
T = int(input())
for i in range(T):
n, m = map(int, input().split())
g = list()
for j in range(n):
g.append(list(map(int, input().split())))
# count计算负数的个数
res = count = 0
# minw求解绝对值最小的值
minw = 10 ** 8
for j in range(n):
for k in range(m):
res += abs(g[j][k])
if g[j][k] < 0:
count += 1
minw = min(minw, abs(g[j][k]))
if count % 2:
# 应该减去两倍的minw
print(res - 2 * minw)
else:
print(res)if __name__ == '__main__':
Solution().process()推荐阅读
- C语言|【sm2算法】基于mbedtls开源库国密算法的使用（二）
- 数据结构-算法|数据结构之红黑树，2-3-4树，插入旋转调整
- 人工智能|参赛指南 ｜ 教育部白名单竞赛少年硅谷 AI算法竞技赛
- LeetCode刷题|高精度乘法的两种实现方式
- #|《大话数据结构》从零开始 —— 第三章（线性表之链式存储结构 （单链表、静态链表、双向链表、循环链表））
- 算法|2021谷歌年度AI技术总结 | Jeff Dean执笔万字展望人工智能的5大未来趋势！
- 数据结构|数据结构基本概念以及线性表的基本操作
- #|数据结构与算法（2-2）线性表之链式存储（单链表、静态链表、循环链表、双向循环链表）
- 剑指offer编程题解法汇总|力扣解法汇总1601- 最多可达成的换楼请求数目