Dada una array bidimensional NxN , la tarea de encontrar la suma de todas las subarrays.
Ejemplos:
Input : arr[] = {{1, 1},
{1, 1}};
Output : 16
Explanation:
Number of sub-matrices with 1 elements = 4
Number of sub-matrices with 2 elements = 4
Number of sub-matrices with 3 elements = 0
Number of sub-matrices with 4 elements = 1
Since all the entries are 1, the sum becomes
sum = 1 * 4 + 2 * 4 + 3 * 0 + 4 * 1 = 16
Input : arr[] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}}
Output : 500
Solución simple: una solución ingenua es generar todas las subarrays posibles y resumirlas todas.
La complejidad temporal de este enfoque será O(n 6 ).
Solución eficiente: para cada elemento de la array, intentemos encontrar el número de subarrays en las que se encontrará el elemento.
Esto se puede hacer en tiempo O (1). Supongamos que el índice de un elemento sea (X, Y) en indexación basada en 0, entonces el número de subarrays (S x, y ) para este elemento estará dado por la fórmula S x, y = (X + 1) * (Y + 1) * (N – X) * (N – Y) . Esta fórmula funciona, porque solo tenemos que elegir dos posiciones diferentes en la array que crearán una subarray que envuelve al elemento. Por lo tanto, para cada elemento, ‘sum’ se puede actualizar como sum += (S x, y ) * Arr x, y .
A continuación se muestra la implementación del enfoque anterior:
Aquí tenemos que tratar de resolver esta pregunta en la técnica de búsqueda inversa :
1) Para un elemento en particular cuales son las posibles subarrays donde se incluirá este elemento .
2) Cuando obtenemos el número de subarrays posibles, podemos contar la contribución de ese elemento en particular haciendo (a[i]* número total de subarrays donde se incluirá) donde a[i] = elemento actual
3) Ahora viene la pregunta de cómo encontrar el número de subarrays posibles para un elemento en particular.
[[1 2 3]
[4 5 6]
[7 8 9]]
Entonces, consideremos el elemento actual como 5, por lo que para 5 hay (X + 1) * (Y + 1) opciones donde pueden estar las coordenadas del punto de inicio de la subarray, (arriba a la izquierda)
De manera similar, habrá opciones (NX)*(NY) donde las coordenadas finales de esa subarray pueden estar (abajo a la derecha)
Número de opciones para Arriba a la izquierda = (X+1)*(Y+1)
Número de opciones para abajo a la derecha = (NX)*(NY)
El número total de opciones para el elemento actual que se incluirá en la subarray será: (X+1)*(Y+1) * (NX)*(NY)
La contribución del elemento actual que se puede incluir en todas las subarrays posibles será = arr[X][Y] * (X+1)*(Y+1) * (NX)*(NY)
donde X e Y son índices de las subarrays.
C++
// C++ program to find the sum of all
// possible submatrices of a given Matrix
#include <iostream>
#define n 3
using namespace std;
// Function to find the sum of all
// possible submatrices of a given Matrix
int matrixSum(int arr[][n])
{
// Variable to store
// the required sum
int sum = 0;
// Nested loop to find the number
// of submatrices, each number belongs to
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
// Number of ways to choose
// from top-left elements
int top_left = (i + 1) * (j + 1);
// Number of ways to choose
// from bottom-right elements
int bottom_right = (n - i) * (n - j);
sum += (top_left * bottom_right * arr[i][j]);
}
return sum;
}
// Driver Code
int main()
{
int arr[][n] = { { 1, 1, 1 },
{ 1, 1, 1 },
{ 1, 1, 1 } };
cout << matrixSum(arr);
return 0;
}
Java
// Java program to find the sum of all
// possible submatrices of a given Matrix
class GFG
{
static final int n = 3;
// Function to find the sum of all
// possible submatrices of a given Matrix
static int matrixSum(int arr[][])
{
// Variable to store
// the required sum
int sum = 0;
// Nested loop to find the number
// of submatrices, each number belongs to
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// Number of ways to choose
// from top-left elements
int top_left = (i + 1) * (j + 1);
// Number of ways to choose
// from bottom-right elements
int bottom_right = (n - i) * (n - j);
sum += (top_left * bottom_right * arr[i][j]);
}
}
return sum;
}
// Driver Code
public static void main(String[] args)
{
int arr[][] = {{1, 1, 1},
{1, 1, 1},
{1, 1, 1}};
System.out.println(matrixSum(arr));
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program to find the sum of all # possible submatrices of a given Matrix n = 3 # Function to find the sum of all # possible submatrices of a given Matrix def matrixSum(arr) : # Variable to store the required sum sum = 0; # Nested loop to find the number of # submatrices, each number belongs to for i in range(n) : for j in range(n) : # Number of ways to choose # from top-left elements top_left = (i + 1) * (j + 1); # Number of ways to choose # from bottom-right elements bottom_right = (n - i) * (n - j); sum += (top_left * bottom_right * arr[i][j]); return sum; # Driver Code if __name__ == "__main__" : arr = [[ 1, 1, 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ]]; print(matrixSum(arr)) # This code is contributed by Ryuga
C#
// C# program to find the sum of all
// possible submatrices of a given Matrix
using System;
class GFG
{
static int n = 3;
// Function to find the sum of all
// possible submatrices of a given Matrix
static int matrixSum(int [,]arr)
{
// Variable to store the
// required sum
int sum = 0;
// Nested loop to find the number of
// submatrices, each number belongs to
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// Number of ways to choose
// from top-left elements
int top_left = (i + 1) * (j + 1);
// Number of ways to choose
// from bottom-right elements
int bottom_right = (n - i) * (n - j);
sum += (top_left * bottom_right * arr[i, j]);
}
}
return sum;
}
// Driver Code
public static void Main()
{
int [,]arr = {{1, 1, 1},
{1, 1, 1},
{1, 1, 1}};
Console.WriteLine(matrixSum(arr));
}
}
// This code contributed by vt_m..
PHP
<?php
// PHP program to find the sum of all
// possible submatrices of a given Matrix
// Function to find the sum of all
// possible submatrices of a given Matrix
function matrixSum($arr)
{
$n = 3;
// Variable to store the required sum
$sum = 0;
// Nested loop to find the number
// of submatrices, each number belongs to
for ($i = 0; $i < $n; $i++)
for ($j = 0; $j < $n; $j++)
{
// Number of ways to choose
// from top-left elements
$top_left = ($i + 1) * ($j + 1);
// Number of ways to choose
// from bottom-right elements
$bottom_right = ($n - $i) * ($n - $j);
$sum += ($top_left * $bottom_right *
$arr[$i][$j]);
}
return $sum;
}
// Driver Code
$arr = array(array(1, 1, 1),
array(1, 1, 1),
array(1, 1, 1));
echo matrixSum($arr);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// JavaScript program to find the sum of all
// possible submatrices of a given Matrix
let n = 3;
// Function to find the sum of all
// possible submatrices of a given Matrix
function matrixSum(arr)
{
// Variable to store
// the required sum
let sum = 0;
// Nested loop to find the number
// of submatrices, each number belongs to
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) {
// Number of ways to choose
// from top-left elements
let top_left = (i + 1) * (j + 1);
// Number of ways to choose
// from bottom-right elements
let bottom_right = (n - i) * (n - j);
sum += (top_left * bottom_right * arr[i][j]);
}
return sum;
}
// Driver Code
let arr = [[ 1, 1, 1 ],
[ 1, 1, 1 ],
[ 1, 1, 1 ]] ;
document.write(matrixSum(arr));
// This code is contributed by todaysgaurav
</script>
100
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA