DEV Community

Cover image for 1975. Maximum Matrix Sum
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

1

1975. Maximum Matrix Sum

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:

pc79-q2ex1

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

pc79-q2ex2

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

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

<?php
/**
 * @param Integer[][] $matrix
 * @return Integer
 */
function maximumMatrixSum($matrix) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test case 1
$matrix1 = [[1, -1], [-1, 1]];
echo "Output: " . maximumMatrixSum($matrix1) . "\n"; // Output: 4

// Test case 2
$matrix2 = [[1, 2, 3], [-1, -2, -3], [1, 2, 3]];
echo "Output: " . maximumMatrixSum($matrix2) . "\n"; // Output: 16
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. 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.
  2. Track Smallest Absolute Value: Use this to adjust the sum when the count of negative numbers is odd.
  3. 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:

Billboard image

Monitoring as code

With Checkly, you can use Playwright tests and Javascript to monitor end-to-end scenarios in your NextJS, Astro, Remix, or other application.

Get started now!

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay