aboutsummaryrefslogtreecommitdiff
path: root/maximum_matrix_sum.py
blob: 1babfdfa4e9ddf7dfc823ea8da9c387f2b7a9e15 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 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 maximise the summation of the
matrix's elements. return maximum sum of the matrix's elements using the
afforementioned operation.
"""


class Solution(object):
    def maxMatrixSum(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        ans, mult, val = 0, 0, float("inf")
        for i in range(len(matrix)):
            for j in range(len(matrix)):
                ans += abs(matrix[i][j])
                val = min(val, abs(matrix[i][j]))
                if matrix[i][j] < 0:
                    mult ^= 1
        return ans - 2 * mult * val


if __name__ == "__main__":
    obj = Solution()
    print(obj.maxMatrixSum(matrix=[[1, -1], [-1, 1]]))
    print(obj.maxMatrixSum(matrix=[[1, 2, 3], [-1, -2, -3], [1, 2, 3]]))