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:
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 |
6
Â
Time Complexity: O(N2)Â
Auxiliary Space: O(1)
Please refer complete article on Maximize sum of diagonal of a matrix by rotating all rows or all columns for more details!
