Formatted question description: https://leetcode.ca/all/1975.html

1975. Maximum Matrix Sum

Level

Medium

Description

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.

Example 1:

Image text

Input: matrix = [[1,-1],[-1,1]]

Output: 4

Explanation: We can follow the following steps to reach sum equals 4:

  • Multiply the 2 elements in the first row by -1.
  • Multiply the 2 elements in the first column by -1.

Example 2:

Image text

Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]

Output: 16

Explanation: We can follow the following step to reach sum equals 16:

  • Multiply the 2 last elements in the second row by -1.

Constraints:

  • n == matrix.length == matrix[i].length
  • 2 <= n <= 250
  • -10^5 <= matrix[i][j] <= 10^5

Solution

To get the maximum matrix sum, at most one element can be negative after performing the operation any number of times. If there is no element 0 and the number of negative elements is odd, then there has to be one negative element. Otherwise, all elements can be non-negative. If there has to be one negative element, it should have the minimum absolute value. Therefore, find the element with the minimum absolute value and make it negative if there has to be one negative element (the element can be positive in the original matrix), and calculate the sum of elements in the matrix.

class Solution {
    public long maxMatrixSum(int[][] matrix) {
        long sum = 0;
        int minPositive = Integer.MAX_VALUE;
        int minNegative = Integer.MIN_VALUE;
        int positiveCount = 0, negativeCount = 0, zeroCount = 0;
        int side = matrix.length;
        for (int i = 0; i < side; i++) {
            for (int j = 0; j < side; j++) {
                int num = matrix[i][j];
                sum += Math.abs(num);
                if (num > 0) {
                    minPositive = Math.min(minPositive, num);
                    positiveCount++;
                } else if (num < 0) {
                    minNegative = Math.max(minNegative, num);
                    negativeCount++;
                } else
                    zeroCount++;
            }
        }
        if (zeroCount > 0 || negativeCount % 2 == 0)
            return sum;
        if (positiveCount == 0)
            return sum += minNegative * 2;
        int minPositiveAbs = minPositive, minNegativeAbs = -minNegative;
        sum -= Math.min(minPositiveAbs, minNegativeAbs) * 2;
        return sum;
    }
}

All Problems

All Solutions