[Leetcode 1975번 문제] 1975. Maximum Matrix Sum

문제 상황

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.

m * n

입력

• n == matrix.length == matrix[i].length
• 2 <= n <= 250
• 105 <= matrix[i][j] <= 105

출력

과정

난 이제 알고있다 이건 1개빼고 전부, 혹은 전부를 뒤집을 수 있다는 뜻이다.

-값인 애들을 전부

개수 :

양수값의 총합

음수값의 총합 :

음수중 가장 큰 수 와 양수중 가장 작은 수 :

그래서 마지막에 개수가 짝수라면 음수값을 -1 곱해서 더하고 반대로 홀수일 경우에 음수중 가장 큰 수와 양수중 가장 작은 수룰 두 고 둘 중에서 절대값이 작은수를 더하는 방식으로 구현한다

알고리즘 개요도

알고리즘

class Solution {
public:
    using ll = long long;

    long long maxMatrixSum(vector<vector<int>>& matrix) {
        ll minNum = INT_MAX;
        ll sum = 0;
        ll numNegative = 0;

        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                numNegative += matrix[i][j] < 0;
                minNum = min(minNum, (ll) abs(matrix[i][j]));
                sum += abs(matrix[i][j]);
            }
        }

        sum -= (minNum * 2) * (numNegative % 2);

        return sum;
    }
};