Given a matrix mat[] of dimension N*N, the task is to find the maximum sum of matrix elements by flipping the signs of the adjacent element any number of times.
Examples:
Input: mat[][] = [[2, -2], [-2, 2]]
OutputL: 8
Explanation:
Follow the steps below to find the maximum sum of matrix as:
- Flipping the sign of adjacent element (arr[0][0], arr[0][1]) modifies the matrix to mat[][] = {{-2, 2}, {-2, 2}}.
- Flipping the sign of adjacent element (arr[0][0], arr[1][0]) modifies the matrix to mat[][] = {{2, 2}, {2, 2}}.
Now, the sum of matrix elements is 8, which is the maximum among all possible flipping of adjacent matrix elements.
Input: mat[][] = [[1, 2, 3], [-1, -2, -3], [1, 2, 3]]
Output: 16
Approach: The given problem can be solved by observing the fact that if there are an even number of negatives in the matrix, then all those elements can be converted to positive elements to get the maximum sum. Otherwise, all matrix elements can be flipped except the one negative elements. Follow the steps below to solve the problem:
- Find the sum of absolute values of all matrix elements and store it in a variable say S.
- Find the matrix element with minimum absolute values and store it in a variable say minElement.
- If the count of negative elements in the given matrix mat[][] is even, then print the maximum sum as S. Otherwise, print the value of (S – 2*minElement) as the resultant sum by excluding the minimum element in the sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of// matrix element after flipping the// signs of adjacent matrix elementsint maxSum(vector<vector<int> >& matrix){ // Initialize row and column int r = matrix.size(); int c = matrix[0].size(); // Stores the sum of absolute // matrix element int sum = 0; // Find the minimum absolute value // in the matrix int mini = INT_MAX; // Store count of negatives int count = 0; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { int k = matrix[i][j]; // Find the smallest absolute // value in the matrix mini = min(mini, abs(k)); // Increment the count of // negative numbers if (k < 0) count++; // Find the absolute sum sum += abs(k); } } // If the count of negatives is // even then print the sum if (count % 2 == 0) { return sum; } // Subtract minimum absolute // element else { return (sum - 2 * mini); }}// Driver Codeint main(){ vector<vector<int> > matrix = { { 2, -2 }, { -2, 2 } }; cout << maxSum(matrix); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find the maximum sum of // matrix element after flipping the // signs of adjacent matrix elements static int maxSum(int[][] matrix) { // Initialize row and column int r = matrix.length; int c = matrix[0].length; // Stores the sum of absolute // matrix element int sum = 0; // Find the minimum absolute value // in the matrix int mini = Integer.MAX_VALUE; // Store count of negatives int count = 0; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { int k = matrix[i][j]; // Find the smallest absolute // value in the matrix mini = Math.min(mini, Math.abs(k)); // Increment the count of // negative numbers if (k < 0) count++; // Find the absolute sum sum += Math.abs(k); } } // If the count of negatives is // even then print the sum if (count % 2 == 0) { return sum; } // Subtract minimum absolute // element else { return (sum - 2 * mini); } } // Driver Code public static void main(String[] args) { int[][] matrix = { { 2, -2 }, { -2, 2 } }; System.out.print(maxSum(matrix)); }}// This code is contributed by subham348. |
Python3
# Python 3 program for the above approachimport sys# Function to find the maximum sum of# matrix element after flipping the# signs of adjacent matrix elementsdef maxSum(matrix): # Initialize row and column r = len(matrix) c = len(matrix[0]) # Stores the sum of absolute # matrix element sum = 0 # Find the minimum absolute value # in the matrix mini = sys.maxsize # Store count of negatives count = 0 for i in range(r): for j in range(c): k = matrix[i][j] # Find the smallest absolute # value in the matrix mini = min(mini, abs(k)) # Increment the count of # negative numbers if (k < 0): count += 1 # Find the absolute sum sum += abs(k) # If the count of negatives is # even then print the sum if (count % 2 == 0): return sum # Subtract minimum absolute # element else: return (sum - 2 * mini)# Driver Codeif __name__ == '__main__': matrix = [[2, -2],[-2, 2]] print(maxSum(matrix)) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find the maximum sum of // matrix element after flipping the // signs of adjacent matrix elements static int maxSum(int[,] matrix) { // Initialize row and column int r = matrix.GetLength(0); int c = matrix.GetLength(1); // Stores the sum of absolute // matrix element int sum = 0; // Find the minimum absolute value // in the matrix int mini = int.MaxValue; // Store count of negatives int count = 0; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { int k = matrix[i,j]; // Find the smallest absolute // value in the matrix mini = Math.Min(mini, Math.Abs(k)); // Increment the count of // negative numbers if (k < 0) count++; // Find the absolute sum sum += Math.Abs(k); } } // If the count of negatives is // even then print the sum if (count % 2 == 0) { return sum; } // Subtract minimum absolute // element else { return (sum - 2 * mini); } } // Driver Code public static void Main(string[] args) { int[,] matrix = { { 2, -2 }, { -2, 2 } }; Console.Write(maxSum(matrix)); }}// This code is contributed by AnkThon |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the maximum sum of // matrix element after flipping the // signs of adjacent matrix elements function maxSum(matrix) { // Initialize row and column let r = matrix.length; let c = matrix[0].length; // Stores the sum of absolute // matrix element let sum = 0; // Find the minimum absolute value // in the matrix let mini = Number.MAX_VALUE; // Store count of negatives let count = 0; for (let i = 0; i < r; i++) { for (let j = 0; j < c; j++) { let k = matrix[i][j]; // Find the smallest absolute // value in the matrix mini = Math.min(mini, Math.abs(k)); // Increment the count of // negative numbers if (k < 0) count++; // Find the absolute sum sum += Math.abs(k); } } // If the count of negatives is // even then print the sum if (count % 2 == 0) { return sum; } // Subtract minimum absolute // element else { return (sum - 2 * mini); } } // Driver Code let matrix = [[2, -2], [-2, 2]]; document.write(maxSum(matrix));// This code is contributed by Potta Lokesh </script> |
Output:
8
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
