Given a square matrix, mat[][] of dimensions N * N, the task is find the maximum sum of diagonal elements possible from the given matrix by rotating either all the rows or all the columns of the matrix by a positive integer.
Examples:
Input: mat[][] = { { 1, 1, 2 }, { 2, 1, 2 }, { 1, 2, 2 } }
Output: 6
Explanation:
Rotating all the columns of matrix by 1 modifies mat[][] to { {2, 1, 2}, {1, 2, 2}, {1, 1, 2} }.
Therefore, the sum of diagonal elements of the matrix = 2 + 2 + 2 = 6 which is the maximum possible.Input: A[][] = { { -1, 2 }, { -1, 3 } }
Output: 2
Approach: The idea is to rotate all the rows and columns of the matrix in all possible ways and calculate the maximum sum obtained. Follow the steps to solve the problem:
- Initialize a variable, say maxDiagonalSum to store the maximum possible sum of diagonal elements the matrix by rotating all the rows or columns of the matrix.
- Rotate all the rows of the matrix by a positive integer in the range [0, N – 1] and update the value of maxDiagonalSum.
- Rotate all the columns of the matrix by a positive integer in the range [0, N – 1] and update the value of maxDiagonalSum.
- Finally, print the value of maxDiagonalSum.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define N 3// Function to find maximum sum of diagonal elements // of matrix by rotating either rows or columnsint findMaximumDiagonalSumOMatrixf(int A[][N]){ // Stores maximum diagonal sum of elements // of matrix by rotating rows or columns int maxDiagonalSum = INT_MIN; // Rotate all the columns by an integer // in the range [0, N - 1] for (int i = 0; i < N; i++) { // Stores sum of diagonal elements // of the matrix int curr = 0; // Calculate sum of diagonal // elements of the matrix for (int j = 0; j < N; j++) { // Update curr curr += A[j][(i + j) % N]; } // Update maxDiagonalSum maxDiagonalSum = max(maxDiagonalSum, curr); } // Rotate all the rows by an integer // in the range [0, N - 1] for (int i = 0; i < N; i++) { // Stores sum of diagonal elements // of the matrix int curr = 0; // Calculate sum of diagonal // elements of the matrix for (int j = 0; j < N; j++) { // Update curr curr += A[(i + j) % N][j]; } // Update maxDiagonalSum maxDiagonalSum = max(maxDiagonalSum, curr); } return maxDiagonalSum;}// Driver codeint main(){ int mat[N][N] = { { 1, 1, 2 }, { 2, 1, 2 }, { 1, 2, 2 } }; cout<< findMaximumDiagonalSumOMatrixf(mat); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{static int N = 3; // Function to find maximum sum of // diagonal elements of matrix by// rotating either rows or columnsstatic int findMaximumDiagonalSumOMatrixf(int A[][]){ // Stores maximum diagonal sum of elements // of matrix by rotating rows or columns int maxDiagonalSum = Integer.MIN_VALUE; // Rotate all the columns by an integer // in the range [0, N - 1] for(int i = 0; i < N; i++) { // Stores sum of diagonal elements // of the matrix int curr = 0; // Calculate sum of diagonal // elements of the matrix for(int j = 0; j < N; j++) { // Update curr curr += A[j][(i + j) % N]; } // Update maxDiagonalSum maxDiagonalSum = Math.max(maxDiagonalSum, curr); } // Rotate all the rows by an integer // in the range [0, N - 1] for(int i = 0; i < N; i++) { // Stores sum of diagonal elements // of the matrix int curr = 0; // Calculate sum of diagonal // elements of the matrix for(int j = 0; j < N; j++) { // Update curr curr += A[(i + j) % N][j]; } // Update maxDiagonalSum maxDiagonalSum = Math.max(maxDiagonalSum, curr); } return maxDiagonalSum;} // Driver Codepublic static void main(String[] args){ int[][] mat = { { 1, 1, 2 }, { 2, 1, 2 }, { 1, 2, 2 } }; System.out.println( findMaximumDiagonalSumOMatrixf(mat));}}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program to implement# the above approachimport sysN = 3# Function to find maximum sum of diagonal# elements of matrix by rotating either # rows or columnsdef findMaximumDiagonalSumOMatrixf(A): # Stores maximum diagonal sum of elements # of matrix by rotating rows or columns maxDiagonalSum = -sys.maxsize - 1 # Rotate all the columns by an integer # in the range [0, N - 1] for i in range(N): # Stores sum of diagonal elements # of the matrix curr = 0 # Calculate sum of diagonal # elements of the matrix for j in range(N): # Update curr curr += A[j][(i + j) % N] # Update maxDiagonalSum maxDiagonalSum = max(maxDiagonalSum, curr) # Rotate all the rows by an integer # in the range [0, N - 1] for i in range(N): # Stores sum of diagonal elements # of the matrix curr = 0 # Calculate sum of diagonal # elements of the matrix for j in range(N): # Update curr curr += A[(i + j) % N][j] # Update maxDiagonalSum maxDiagonalSum = max(maxDiagonalSum, curr) return maxDiagonalSum# Driver codeif __name__ == "__main__": mat = [ [ 1, 1, 2 ], [ 2, 1, 2 ], [ 1, 2, 2 ] ] print(findMaximumDiagonalSumOMatrixf(mat)) # This code is contributed by chitranayal |
C#
// C# program to implement// the above approach using System; class GFG{ static int N = 3; // Function to find maximum sum of // diagonal elements of matrix by// rotating either rows or columnsstatic int findMaximumDiagonalSumOMatrixf(int[,] A){ // Stores maximum diagonal sum of elements // of matrix by rotating rows or columns int maxDiagonalSum = Int32.MinValue; // Rotate all the columns by an integer // in the range [0, N - 1] for(int i = 0; i < N; i++) { // Stores sum of diagonal elements // of the matrix int curr = 0; // Calculate sum of diagonal // elements of the matrix for(int j = 0; j < N; j++) { // Update curr curr += A[j, (i + j) % N]; } // Update maxDiagonalSum maxDiagonalSum = Math.Max(maxDiagonalSum, curr); } // Rotate all the rows by an integer // in the range [0, N - 1] for(int i = 0; i < N; i++) { // Stores sum of diagonal elements // of the matrix int curr = 0; // Calculate sum of diagonal // elements of the matrix for(int j = 0; j < N; j++) { // Update curr curr += A[(i + j) % N, j]; } // Update maxDiagonalSum maxDiagonalSum = Math.Max(maxDiagonalSum, curr); } return maxDiagonalSum;} // Driver Codepublic static void Main(){ int[,] mat = { { 1, 1, 2 }, { 2, 1, 2 }, { 1, 2, 2 } }; Console.Write(findMaximumDiagonalSumOMatrixf(mat));}}// This code is contributed by code_hunt |
Javascript
<script>// Javascript program to implement// the above approachlet N = 3; // Function to find maximum sum of// diagonal elements of matrix by// rotating either rows or columnsfunction findMaximumDiagonalSumOMatrixf(A){ // Stores maximum diagonal sum of elements // of matrix by rotating rows or columns let maxDiagonalSum = Number.MIN_VALUE; // Rotate all the columns by an integer // in the range [0, N - 1] for(let i = 0; i < N; i++) { // Stores sum of diagonal elements // of the matrix let curr = 0; // Calculate sum of diagonal // elements of the matrix for(let j = 0; j < N; j++) { // Update curr curr += A[j][(i + j) % N]; } // Update maxDiagonalSum maxDiagonalSum = Math.max(maxDiagonalSum, curr); } // Rotate all the rows by an integer // in the range [0, N - 1] for(let i = 0; i < N; i++) { // Stores sum of diagonal elements // of the matrix let curr = 0; // Calculate sum of diagonal // elements of the matrix for(let j = 0; j < N; j++) { // Update curr curr += A[(i + j) % N][j]; } // Update maxDiagonalSum maxDiagonalSum = Math.max(maxDiagonalSum, curr); } return maxDiagonalSum;} // Driver Code let mat = [[ 1, 1, 2 ], [ 2, 1, 2 ], [ 1, 2, 2 ]]; document.write( findMaximumDiagonalSumOMatrixf(mat));// This code is contributed by souravghosh0416.</script> |
Output:
6
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!
