Maximum Matrix Sum

Leetcode Problem:

• Maximum Matrix Sum

Summary

• Given an n x n matrix, find the maximum sum of its elements by multiplying adjacent elements by -1.

Approach

• The solution works by first calculating the sum of the absolute values of all elements in the matrix
• Then, it checks if there is an even number of negative elements
• If there is, it subtracts twice the minimum value from the sum
• This operation effectively flips the sign of the negative elements, which can increase the sum.

Complexity

• O(n^2) where n is the size of the matrix

Explanation

• The solution iterates over each element in the matrix once to calculate the sum and count the number of negative elements
• Then, it checks if there is an odd number of negative elements and subtracts twice the minimum value from the sum if necessary
• This approach ensures that the maximum sum is achieved by flipping the sign of the negative elements.

Solution Code:

class Solution {
public:
    long long maxMatrixSum(vector>& matrix) {
        int cnt = 0;
        int minValue = 100001;
        long long sum = 0;
        bool isZero = false;
        for(int i = 0 ; i < matrix.size(); i++){
            for(int j = 0 ; j < matrix[0].size(); j++){
                sum += abs(matrix[i][j]);
                if(matrix[i][j] < 0){
                    cnt++;
                }
                minValue = min(minValue, abs(matrix[i][j]));
                if(matrix[i][j] == 0){
                    isZero = true;
                }
            }
        }
        if(!isZero && (cnt &1)){
            sum -= minValue*2;
        }
        return sum;
    }
};