1. 문제 소개

1975. Maximum Matrix Sum

2. 나의 풀이

문제에 나온 규칙대로라면 음수의 개수에 따라 답이 달라진다.
음수의 개수가 짝수라면 그냥 모든 entry의 절대값을 더하고, 홀수라면 절대값이 가장 낮은 것만 세면 된다.
다른 문제들도 이와 같은 로직을 사용해 풀었다.
시간복잡도는 $O(n^2)$이다.

class Solution:                                             # LeetCode 제출 형식에 맞춘 Solution 클래스 정의
    def maxMatrixSum(self, matrix: List[List[int]]) -> int: # 행렬에서 만들 수 있는 최대 합을 계산하는 함수
        cnt = 0                                             # 음수 원소의 개수를 세기 위한 변수
        ans = 0                                             # 모든 원소 절댓값의 합을 누적할 변수
        min_val = 10**6                                     # 원소 절댓값 중 최솟값을 저장할 변수 초기화
        
        for row in matrix:                                  # 행렬의 각 행을 순회
            for val in row:                                 # 각 행의 원소를 하나씩 순회
                ans += abs(val)                             # 현재 원소의 절댓값을 전체 합에 더함
                if val < 0:                                 # 현재 원소가 음수인 경우
                    cnt += 1                                # 음수 개수를 1 증가
                min_val = min(abs(val), min_val)           # 절댓값의 최소값을 갱신
        
        if cnt % 2 != 0:                                    # 음수 개수가 홀수인 경우
            ans -= 2 * min_val                              # 가장 작은 절댓값을 두 번 빼서 하나를 음수로 유지
        
        return ans                                          # 계산된 최대 행렬 합을 반환

3. 다른 풀이

내 풀이와 논리가 같다.

4. 마무리

잘 풀었다.