1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
/// 1975. Maximum Matrix Sum (Medium)
///
/// You are given an n x n integer matrix. You can do the following operation
/// *any* number of times:
///
/// * Choose any two *adjacent* elements of matrix and *multiply* each of them
/// by -1.
///
/// Two elements are considered *adjacent* if and only if they share a *border*.
///
/// Your goal is to *maximize* the summation of the matrix's elements. Return
/// the *maximum* sum of the matrix's elements using the operation mentioned
/// above.
///
/// *Example 1:*
///
/// *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.
///
/// *Example 2:*
///
/// *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.
///
/// *Constraints:*
///
/// * n == matrix.length == matrix[i].length
/// * 2 <= n <= 250
/// * -105 <= matrix[i][j] <= 105
///
use leetcode::*;
struct Solution {}
impl Solution {
pub fn max_matrix_sum(matrix: Vec<Vec<i32>>) -> i64 {
let mut min = i32::MAX;
let mut count = 0usize;
let mut sum = 0i64;
let mut zero = false;
for row in matrix {
for entry in row {
sum += entry.abs() as i64;
min = min.min(entry.abs());
zero |= entry == 0;
count += (entry < 0) as usize;
}
}
if !zero && count % 2 == 1 {
sum -= 2 * min as i64;
}
sum
}
}
pub fn main() {
println!("{:?}", Solution::max_matrix_sum(arg_into(1)));
}
#[cfg(test)]
mod tests {
use crate::Solution;
use leetcode::vvi;
#[test]
fn test() {
assert_eq!(Solution::max_matrix_sum(vvi("[[1,-1],[-1,1]]")), 4);
assert_eq!(
Solution::max_matrix_sum(vvi("[[1,2,3],[-1,-2,-3],[1,2,3]]")),
16
);
}
}
|
