Aumento máximo en el valor de Matrix para mantener el máximo de filas y columnas sin cambios

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:
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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *