[LeetCode] 1975. Maximum Matrix Sum - 구현

문제 링크 : https://leetcode.com/problems/maximum-matrix-sum/description/

🍊해결방법

• 인접한 두개의 구역(행 or 열)을 정해서 -1을 곱하여 수를 변경하고 행렬 전체의 최대값을 구하여라
• 음수의 개수가 짝수개면 최종적으로 음수의 개수가 없다
• 음수의 개수가 홀수라면 마지막 1개만 음수가 남는다
• 행렬을 탐색하면서 절대값을 sum에 더하고, 최솟값을 갱신한다
• 음수의 개수가 홀수개면 최솟값이 음수가 되면 되므로 sum에서 빼준다

😀풀이

import java.util.*;

class Solution {
    public long maxMatrixSum(int[][] matrix) {

        // 음수인 수의 개수를 관리하자
        // 결국은 음수개수가 짝수개면 상관없고
        // 홀수개일 때 젤 작은 절대값을 가진 놈을 전체 합에서 빼주면 된다

        int cnt = 0;
        int min = 100010;

        long sum = 0;

        int n = matrix.length;

        

        for(int i=0; i<n; i++){
            for(int j=0; j<matrix[i].length; j++){
                if(matrix[i][j] < 0){
                    cnt++;
                }

                min = Math.min(min, Math.abs(matrix[i][j]));

                sum += Math.abs(matrix[i][j]);
            }
        }

        if(cnt%2 != 0){
            sum -= 2*min;
        }
        
        return sum;
    }
}