Diferencia máxima de suma de elementos en dos filas en una array

Posted on by Rudeus Greyrat

Dada una array de orden m*n, la tarea es encontrar la diferencia máxima entre dos filas Rj y Ri tal que i < j, es decir, necesitamos encontrar el valor máximo de sum(Rj) – sum(Ri) tal que la fila i está por encima de la fila j.

Ejemplos: 

Input : mat[5][4] = {{-1, 2, 3, 4},
                     {5, 3, -2, 1},
                     {6, 7, 2, -3},
                     {2, 9, 1, 4},
                     {2, 1, -2, 0}}
Output: 9
// difference of R3 - R1 is maximum

Una solución simple para este problema es seleccionar una por una cada fila, calcular la suma de los elementos en ella y tomar la diferencia de la suma de las filas siguientes en la dirección de avance. Finalmente devuelva la diferencia máxima. La complejidad del tiempo para este enfoque será O(n*m 2 ).

Una solución eficiente para este problema es calcular primero la suma de todos los elementos de cada fila y almacenarlos en una array auxiliar rowSum[] y luego calcular la diferencia máxima de dos elementos max(rowSum[j] – rowSum[i]) tales que rowSum[i] <rowSum[j] en tiempo lineal. Ver este artículo. En este método, necesitamos hacer un seguimiento de 2 cosas: 

  1. Diferencia máxima encontrada hasta ahora (max_diff). 
  2. Número mínimo visitado hasta ahora (min_element). 

Implementación:

C++

// C++ program to find maximum difference of sum of
// elements of two rows
#include<bits/stdc++.h>
#define MAX 100
using namespace std;
 
// Function to find maximum difference of sum of
// elements of two rows such that second row appears
// before first row.
int maxRowDiff(int mat[][MAX], int m, int n)
{
    // auxiliary array to store sum of all elements
    // of each row
    int rowSum[m];
 
    // calculate sum of each row and store it in
    // rowSum array
    for (int i=0; i<m; i++)
    {
        int sum = 0;
        for (int j=0; j<n; j++)
            sum += mat[i][j];
        rowSum[i] = sum;
    }
 
    // calculating maximum difference of two elements
    // such that rowSum[i]<rowsum[j]
    int max_diff = rowSum[1] - rowSum[0];
    int min_element = rowSum[0];
    for (int i=1; i<m; i++)
    {
        // if current difference is greater than
        // previous then update it
        if (rowSum[i] - min_element > max_diff)
            max_diff = rowSum[i] - min_element;
 
        // if new element is less than previous minimum
        // element then update it so that
        // we may get maximum difference in remaining array
        if (rowSum[i] < min_element)
            min_element = rowSum[i];
    }
 
    return max_diff;
}
 
// Driver program to run the case
int main()
{
    int m = 5, n = 4;
    int mat[][MAX] = {{-1, 2, 3, 4},
                     {5, 3, -2, 1},
                     {6, 7, 2, -3},
                     {2, 9, 1, 4},
                     {2, 1, -2, 0}};
 
    cout << maxRowDiff(mat, m, n);
    return 0;
}

C

// C program to find maximum difference of sum of
// elements of two rows
#include <stdio.h>
 
#define MAX 100
 
// Function to find maximum difference of sum of
// elements of two rows such that second row appears
// before first row.
int maxRowDiff(int mat[][MAX], int m, int n)
{
    // auxiliary array to store sum of all elements
    // of each row
    int rowSum[m];
 
    // calculate sum of each row and store it in
    // rowSum array
    for (int i=0; i<m; i++)
    {
        int sum = 0;
        for (int j=0; j<n; j++)
            sum += mat[i][j];
        rowSum[i] = sum;
    }
 
    // calculating maximum difference of two elements
    // such that rowSum[i]<rowsum[j]
    int max_diff = rowSum[1] - rowSum[0];
    int min_element = rowSum[0];
    for (int i=1; i<m; i++)
    {
        // if current difference is greater than
        // previous then update it
        if (rowSum[i] - min_element > max_diff)
            max_diff = rowSum[i] - min_element;
 
        // if new element is less than previous minimum
        // element then update it so that
        // we may get maximum difference in remaining array
        if (rowSum[i] < min_element)
            min_element = rowSum[i];
    }
 
    return max_diff;
}
 
// Driver program to run the case
int main()
{
    int m = 5, n = 4;
    int mat[][MAX] = {{-1, 2, 3, 4},
                     {5, 3, -2, 1},
                     {6, 7, 2, -3},
                     {2, 9, 1, 4},
                     {2, 1, -2, 0}};
    printf("%d",maxRowDiff(mat, m, n));
   
    return 0;
}
 
// This code is contributed by kothavvsaakash.

Java

// Java program to find maximum difference
// of sum of elements of two rows
class GFG {
static final int MAX = 100;
 
// Function to find maximum difference of sum
// of elements of two rows such that second
// row appears before first row.
static int maxRowDiff(int mat[][], int m, int n) {
 
    // auxiliary array to store sum
    // of all elements of each row
    int rowSum[] = new int[m];
 
    // calculate sum of each row and
    // store it in rowSum array
    for (int i = 0; i < m; i++) {
    int sum = 0;
    for (int j = 0; j < n; j++)
        sum += mat[i][j];
    rowSum[i] = sum;
    }
 
    // calculating maximum difference of two elements
    // such that rowSum[i]<rowsum[j]
    int max_diff = rowSum[1] - rowSum[0];
    int min_element = rowSum[0];
    for (int i = 1; i < m; i++) {
 
    // if current difference is greater than
    // previous then update it
    if (rowSum[i] - min_element > max_diff)
        max_diff = rowSum[i] - min_element;
 
    // if new element is less than previous
    // minimum element then update it so that
    // we may get maximum difference in remaining array
    if (rowSum[i] < min_element)
        min_element = rowSum[i];
    }
 
    return max_diff;
}
 
// Driver code
public static void main(String[] args) {
    int m = 5, n = 4;
    int mat[][] = {{-1, 2,  3, 4 },
                     {5,  3, -2, 1 },
                    {6,  7,  2, -3},
                   {2,  9,  1, 4 },
                   {2,  1, -2, 0}};
 
    System.out.print(maxRowDiff(mat, m, n));
}
}
// This code is contributed by Anant Agarwal.

Python3

# Python3 program to find maximum difference
# of sum of elements of two rows
 
# Function to find maximum difference of
# sum of elements of two rows such that
# second row appears before first row.
def maxRowDiff(mat, m, n):
     
    # auxiliary array to store sum of
    # all elements of each row
    rowSum = [0] * m
     
    # calculate sum of each row and
    # store it in rowSum array
    for i in range(0, m):
        sum = 0
        for j in range(0, n):
            sum += mat[i][j]
        rowSum[i] = sum
     
    # calculating maximum difference of
    # two elements such that
    # rowSum[i]<rowsum[j]
    max_diff = rowSum[1] - rowSum[0]
    min_element = rowSum[0]
     
    for i in range(1, m):
     
        # if current difference is greater
        # than previous then update it
        if (rowSum[i] - min_element > max_diff):
            max_diff = rowSum[i] - min_element
         
        # if new element is less than previous
        # minimum element then update it so
        # that we may get maximum difference
        # in remaining array
        if (rowSum[i] < min_element):
            min_element = rowSum[i]
    return max_diff
 
# Driver program to run the case
m = 5
n = 4
mat = [[-1, 2, 3, 4],
       [5, 3, -2, 1],
       [6, 7, 2, -3],
       [2, 9, 1, 4],
       [2, 1, -2, 0]]
 
print( maxRowDiff(mat, m, n))
 
# This code is contributed by Swetank Modi

C#

// C# program to find maximum difference
// of sum of elements of two rows
using System;
 
class GFG {
     
    // Function to find maximum difference
    // of sum of elements of two rows such
    // that second row appears before
    // first row.
    static int maxRowDiff(int [,] mat,
                              int m, int n)
    {
     
        // auxiliary array to store sum
        // of all elements of each row
        int [] rowSum = new int[m];
     
        // calculate sum of each row and
        // store it in rowSum array
        for (int i = 0; i < m; i++)
        {
            int sum = 0;
             
            for (int j = 0; j < n; j++)
                sum += mat[i,j];
                 
            rowSum[i] = sum;
        }
     
        // calculating maximum difference
        // of two elements such that
        // rowSum[i] < rowsum[j]
        int max_diff = rowSum[1] - rowSum[0];
        int min_element = rowSum[0];
         
        for (int i = 1; i < m; i++)
        {
     
            // if current difference is
            // greater than previous then
            // update it
            if (rowSum[i] - min_element
                                  > max_diff)
                max_diff = rowSum[i]
                             - min_element;
         
            // if new element is less than
            // previous minimum element then
            // update it so that we may get
            // maximum difference in
            // remaining array
            if (rowSum[i] < min_element)
                min_element = rowSum[i];
        }
     
        return max_diff;
    }
     
    // Driver code
    public static void Main()
    {
        int m = 5, n = 4;
        int [,] mat = { {-1, 2, 3, 4 },
                        {5, 3, -2, 1 },
                        {6, 7, 2, -3},
                        {2, 9, 1, 4 },
                        {2, 1, -2, 0} };
     
        Console.Write(maxRowDiff(mat, m, n));
    }
}
 
// This code is contributed by KRV.

PHP

<?php
// PHP program to find maximum
// difference of sum of
// elements of two rows
$MAX = 100;
 
// Function to find maximum
// difference of sum of
// elements of two rows such
// that second row appears
// before first row.
function maxRowDiff($mat, $m, $n)
{
    global $MAX;
    // auxiliary array to store
    // sum of all elements
    // of each row
    $rowSum = array();
 
    // calculate sum of each
    // row and store it in
    // rowSum array
    for ($i = 0; $i < $m; $i++)
    {
        $sum = 0;
        for ($j = 0; $j < $n; $j++)
            $sum += $mat[$i][$j];
        $rowSum[$i] = $sum;
    }
 
    // calculating maximum
    // difference of two
    // elements such that
    // rowSum[i]<rowsum[j]
    $max_diff = $rowSum[1] - $rowSum[0];
    $min_element = $rowSum[0];
    for ($i = 1; $i < $m; $i++)
    {
        // if current difference
        // is greater than
        // previous then update it
        if ($rowSum[$i] - $min_element > $max_diff)
            $max_diff = $rowSum[$i] - $min_element;
 
        // if new element is less
        // than previous minimum
        // element then update it
        // so that we may get maximum
        // difference in remaining array
        if ($rowSum[$i] < $min_element)
            $min_element = $rowSum[$i];
    }
 
    return $max_diff;
}
 
// Driver Code
$m = 5;
$n = 4;
$mat = array(array(-1, 2, 3, 4),
             array(5, 3, -2, 1),
             array(6, 7, 2, -3),
             array(2, 9, 1, 4),
             array(2, 1, -2, 0));
 
echo maxRowDiff($mat, $m, $n);
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// Javascript program to find maximum difference
// of sum of elements of two rows
 
// Function to find maximum difference
// of sum of elements of two rows such
// that second row appears before
// first row.
function maxRowDiff(mat, m, n)
{
   
    // Auxiliary array to store sum
    // of all elements of each row
    let rowSum = new Array(m);
   
    // Calculate sum of each row and
    // store it in rowSum array
    for(let i = 0; i < m; i++)
    {
        let sum = 0;
           
        for(let j = 0; j < n; j++)
            sum += mat[i][j];
               
        rowSum[i] = sum;
    }
   
    // Calculating maximum difference
    // of two elements such that
    // rowSum[i] < rowsum[j]
    let max_diff = rowSum[1] - rowSum[0];
    let min_element = rowSum[0];
       
    for(let i = 1; i < m; i++)
    {
   
        // If current difference is
        // greater than previous then
        // update it
        if (rowSum[i] - min_element > max_diff)
            max_diff = rowSum[i] - min_element;
       
        // If new element is less than
        // previous minimum element then
        // update it so that we may get
        // maximum difference in
        // remaining array
        if (rowSum[i] < min_element)
            min_element = rowSum[i];
    }
    return max_diff;
}
 
// Driver code
let m = 5, n = 4;
let mat = [ [ -1, 2, 3, 4 ],
            [ 5, 3, -2, 1 ],
            [ 6, 7, 2, -3 ],
            [ 2, 9, 1, 4  ],
            [ 2, 1, -2, 0 ] ];
 
document.write(maxRowDiff(mat, m, n));
 
// This code is contributed by divyesh072019  
 
</script>
Producción

9

Complejidad temporal : O(m*n) 
Espacio auxiliar : O(m)

Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *