Dada una array cuadrada , mat[][] de dimensiones N * N , la tarea es encontrar la suma máxima posible de elementos diagonales de la array dada al rotar todas las filas o todas las columnas de la array por un número entero positivo.
Ejemplos:
Entrada: mat[][] = { { 1, 1, 2 }, { 2, 1, 2 }, { 1, 2, 2 } }
Salida: 6
Explicación:
Rotar todas las columnas de matrix por 1 modifica mat[] [] a { {2, 1, 2}, {1, 2, 2}, {1, 1, 2} }.
Por tanto, la suma de los elementos de la diagonal de la array = 2 + 2 + 2 = 6 que es el máximo posible.Entrada: A[][] = { { -1, 2 }, { -1, 3 } }
Salida: 2
Planteamiento: La idea es rotar todas las filas y columnas de la array de todas las formas posibles y calcular la suma máxima obtenida. Siga los pasos para resolver el problema:
- Inicialice una variable, digamos maxDiagonalSum para almacenar la suma máxima posible de elementos diagonales de la array rotando todas las filas o columnas de la array.
- Gire todas las filas de la array por un entero positivo en el rango [0, N – 1] y actualice el valor de maxDiagonalSum .
- Rote todas las columnas de la array por un entero positivo en el rango [0, N – 1] y actualice el valor de maxDiagonalSum .
- Finalmente, imprima el valor de maxDiagonalSum .
A continuación se muestra la implementación del enfoque anterior:
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 columns
int 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 code
int 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 columns
static 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 Code
public 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 approach import sys N = 3 # Function to find maximum sum of diagonal # elements of matrix by rotating either # rows or columns def 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 code if __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 columns
static 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 Code
public 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 approach
let N = 3;
// Function to find maximum sum of
// diagonal elements of matrix by
// rotating either rows or columns
function 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>
Producción:
6
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA