2026-01-05 12:30:08 +0300 MSK

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        heap = []
        min_pos = float("inf")
        res = 0
        for row in matrix:
            for col in row:
                if col < 0:
                    heapq.heappush(heap, col)
                else:
                    res += col
                    min_pos = min(min_pos, col)
        while len(heap) >= 2:
            res += -(heapq.heappop(heap) + heapq.heappop(heap))
        if not heap:
            return res
        last = heap.pop()
        if min_pos == float("inf"):
            return res + last
        return max(res + last, (res - min_pos) - (min_pos + last))