/// 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
        );
    }
}