Dada una array mat[][] de dimensión M*N , la tarea es encontrar el máximo valor total posible que debe aumentarse en cada celda (digamos mat[i][j] ) de tal manera que el elemento máximo de la fila i y la columna j permanece sin cambios.
Ejemplos:
Entrada: N = 3, M = 3, mat[][] = { {4, 1, 3}, {3, 1, 1}, {2, 2, 0} }
Salida: 6
Explicación:
La array dada es:
4 1 3
3 1 1
2 2 0
Los valores máximos por fila son: {4, 3, 2}
Los valores máximos por columna son: {4, 2, 3}
Después de aumentar los elementos sin afectar la fila Valores máximos por columna y por columna:
4 2 3
3 2 3
2 2 2
El aumento total en las celdas correspondientes de las dos arrays es ((0 + 1 + 0) + (0 + 1 + 2) + (0 + 0 + 2)) = 6.Entrada: M = 4, N = 4, mat[][] = { {3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3}, {0, 3, 1, 0} }
Salida: 35
Explicación:
La array dada es:
3 0 8 4
2 4 5 7
9 2 6 3
0 3 1 0
Los valores máximos por fila son: {8, 7, 9, 3}
Columna los valores máximos por filas son: {9, 4, 8, 7}
Después de aumentar los elementos sin afectar los valores máximos por filas y columnas:
8 4 8 7
7 4 7 7
9 4 8 7
3 3 3 3
El total el aumento en las celdas correspondientes de las dos arrays es ((5 + 4 + 0 + 3) + (5 + 0 + 2 + 0) + (0 + 2 + 2 + 4) + (3 + 0 + 2 + 3)) = 35.
Acercarse:
- Recorra cada fila y columna de la array dada para almacenar los valores máximos para cada fila y columna.
- Recorra la array dada mat[][] y para cada celda (digamos mat[i][j] ) y agregue la diferencia entre el elemento actual y el valor mínimo de los valores máximos a lo largo de su fila y columna correspondiente como:
diferencia = min(fila[i], cols[j]) – mat[i][j]
- Los valores totales agregados en las operaciones anteriores es el resultado requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum increment
// in each cell of the given matrix such
// that maximum and minimum value remains
// unaffected
int maxIncrease(vector<vector<int> >& matrix)
{
// Get the row of matrix as M
int M = matrix.size();
// Get the column of matrix as N
int N = matrix[0].size();
// To store the row-wise
// maximum values
vector<int> maxRowVal(M, 0);
// To store the column-wise
// maximum values
vector<int> maxColVal(N, 0);
// Traverse along the matrix
// to store the maximum values
// of each row and column
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
// Store the row-wise
// maximum values
maxRowVal[i] = max(maxRowVal[i],
matrix[i][j]);
// Store the column-wise
// maximum values
maxColVal[j] = max(maxColVal[j],
matrix[i][j]);
}
}
// Calculate the total amount
// of increment
int totalIncrease = 0;
// Traverse matrix mat[][]
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
// The maximum possible
// amount to increase
int needToIncrease
= min(maxRowVal[i],
maxColVal[j])
- matrix[i][j];
// Total increased value
totalIncrease += needToIncrease;
}
}
// Return the total
// increased value
return totalIncrease;
}
// Driver Code
int main()
{
// Given matrix
vector<vector<int> > matrix{ { 3, 0, 8, 4 },
{ 2, 4, 5, 7 },
{ 9, 2, 6, 3 },
{ 0, 3, 1, 0 } };
// Function Call
cout << maxIncrease(matrix)
<< endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum increment
// in each cell of the given matrix such
// that maximum and minimum value remains
// unaffected
static int maxIncrease(int [][] matrix)
{
// Get the row of matrix as M
int M = matrix.length;
// Get the column of matrix as N
int N = matrix[0].length;
// To store the row-wise
// maximum values
int []maxRowVal = new int[M];
// To store the column-wise
// maximum values
int []maxColVal = new int[N];
// Traverse along the matrix
// to store the maximum values
// of each row and column
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
// Store the row-wise
// maximum values
maxRowVal[i] = Math.max(maxRowVal[i],
matrix[i][j]);
// Store the column-wise
// maximum values
maxColVal[j] = Math.max(maxColVal[j],
matrix[i][j]);
}
}
// Calculate the total amount
// of increment
int totalIncrease = 0;
// Traverse matrix mat[][]
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
// The maximum possible
// amount to increase
int needToIncrease = Math.min(maxRowVal[i],
maxColVal[j]) -
matrix[i][j];
// Total increased value
totalIncrease += needToIncrease;
}
}
// Return the total
// increased value
return totalIncrease;
}
// Driver Code
public static void main(String[] args)
{
// Given matrix
int [][] matrix = { { 3, 0, 8, 4 },
{ 2, 4, 5, 7 },
{ 9, 2, 6, 3 },
{ 0, 3, 1, 0 } };
// Function Call
System.out.print(maxIncrease(matrix) + "\n");
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach # Function to find the maximum increment # in each cell of the given matrix such # that maximum and minimum value remains # unaffected def maxIncrease(matrix): # Get the row of matrix as M M = len(matrix) # Get the column of matrix as N N = len(matrix[0]) # To store the row-wise # maximum values maxRowVal = [0] * M # To store the column-wise # maximum values maxColVal = [0] * (N) # Traverse along the matrix # to store the maximum values # of each row and column for i in range(M): for j in range(N): # Store the row-wise # maximum values maxRowVal[i] = max(maxRowVal[i], matrix[i][j]) # Store the column-wise # maximum values maxColVal[j] = max(maxColVal[j], matrix[i][j]) # Calculate the total amount # of increment totalIncrease = 0 # Traverse matrix mat[][] for i in range(M): for j in range(N): # The maximum possible # amount to increase needToIncrease = (min(maxRowVal[i], maxColVal[j]) - matrix[i][j]) # Total increased value totalIncrease += needToIncrease # Return the total # increased value return totalIncrease # Driver Code if __name__ == '__main__': # Given matrix matrix = [ [ 3, 0, 8, 4 ], [ 2, 4, 5, 7 ], [ 9, 2, 6, 3 ], [ 0, 3, 1, 0 ] ] # Function call print(maxIncrease(matrix)) # This code is contributed mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum increment
// in each cell of the given matrix such
// that maximum and minimum value remains
// unaffected
static int maxIncrease(int [,] matrix)
{
// Get the row of matrix as M
int M = matrix.GetLength(0);
// Get the column of matrix as N
int N = matrix.GetLength(1);
// To store the row-wise
// maximum values
int []maxRowVal = new int[M];
// To store the column-wise
// maximum values
int []maxColVal = new int[N];
// Traverse along the matrix
// to store the maximum values
// of each row and column
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
// Store the row-wise
// maximum values
maxRowVal[i] = Math.Max(maxRowVal[i],
matrix[i, j]);
// Store the column-wise
// maximum values
maxColVal[j] = Math.Max(maxColVal[j],
matrix[i, j]);
}
}
// Calculate the total amount
// of increment
int totalIncrease = 0;
// Traverse matrix [,]mat
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
// The maximum possible
// amount to increase
int needToIncrease = Math.Min(maxRowVal[i],
maxColVal[j]) -
matrix[i, j];
// Total increased value
totalIncrease += needToIncrease;
}
}
// Return the total
// increased value
return totalIncrease;
}
// Driver Code
public static void Main(String[] args)
{
// Given matrix
int [,] matrix = { { 3, 0, 8, 4 },
{ 2, 4, 5, 7 },
{ 9, 2, 6, 3 },
{ 0, 3, 1, 0 } };
// Function call
Console.Write(maxIncrease(matrix) + "\n");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum increment
// in each cell of the given matrix such
// that maximum and minimum value remains
// unaffected
function maxIncrease(matrix)
{
// Get the row of matrix as M
var M = matrix.length;
// Get the column of matrix as N
var N = matrix[0].length;
// To store the row-wise
// maximum values
var maxRowVal = Array(M).fill(0);
// To store the column-wise
// maximum values
var maxColVal = Array(N).fill(0);
// Traverse along the matrix
// to store the maximum values
// of each row and column
for (var i = 0; i < M; i++) {
for (var j = 0; j < N; j++) {
// Store the row-wise
// maximum values
maxRowVal[i] = Math.max(maxRowVal[i],
matrix[i][j]);
// Store the column-wise
// maximum values
maxColVal[j] = Math.max(maxColVal[j],
matrix[i][j]);
}
}
// Calculate the total amount
// of increment
var totalIncrease = 0;
// Traverse matrix mat[][]
for (var i = 0; i < M; i++) {
for (var j = 0; j < N; j++) {
// The maximum possible
// amount to increase
var needToIncrease
= Math.min(maxRowVal[i],
maxColVal[j])
- matrix[i][j];
// Total increased value
totalIncrease += needToIncrease;
}
}
// Return the total
// increased value
return totalIncrease;
}
// Driver Code
// Given matrix
var matrix = [ [ 3, 0, 8, 4 ],
[ 2, 4, 5, 7 ],
[ 9, 2, 6, 3 ],
[ 0, 3, 1, 0 ] ];
// Function Call
document.write( maxIncrease(matrix) + "<br>");
// This code is contributed by noob2000.
</script>
Producción:
35
Complejidad de tiempo: O(M*N)
Publicación traducida automáticamente
Artículo escrito por goodday451999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA