I am the Great Matrix

1975. Maximum Matrix Sum

Difficulty: Medium

Topics: Array, Greedy, Matrix

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:

• 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:

• 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⁵ <= matrix[i][j] <= 10⁵

Hint:

1. Try to use the operation so that each row has only one negative number.
2. If you have only one negative element you cannot convert it to positive.

Solution:

To maximize the matrix's sum using the operation, we need to minimize the absolute value of the negative contributions to the sum. Here's the plan:

1. Count Negative Numbers: Track how many negative numbers are present in the matrix.
2. Find Minimum Absolute Value: Determine the smallest absolute value in the matrix, which will help if the number of negatives is odd.
3. Adjust for Odd Negatives: If the count of negative numbers is odd, the smallest absolute value cannot be flipped to positive, and this limits the maximum possible sum.

Let's implement this solution in PHP: 1975. Maximum Matrix Sum

  
  
  Explanation:




Summation of Absolute Values: Compute the sum of absolute values of all elements since the optimal configuration flips as many negative numbers to positive as possible.

Track Smallest Absolute Value: Use this to adjust the sum when the count of negative numbers is odd.

Handle Odd Negatives: Subtract twice the smallest absolute value from the sum to account for the unavoidable negative element when the negatives cannot be fully neutralized.



  
  
  Complexity




Time Complexity: O(n^2), as the matrix is traversed once.

Space Complexity: O(1), since no additional space is used apart from variables.


This solution works efficiently within the given constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:


LinkedIn
GitHub



          

            
  

            
        
The above is the detailed content of I am the Great Matrix. For more information, please follow other related articles on the PHP Chinese website!