Сумма всех подматриц данной матрицы

Опубликовано: 14 Января, 2022

Учитывая NxN 2-D матрица, задача найти сумму всех подматрицы.
Примеры:

 Ввод: arr [] = {{1, 1},
                  {1, 1}};
Выход: 16
Пояснение : 
Количество подматриц с 1 элементом = 4
Количество подматриц с 2 элементами = 4
Количество подматриц с 3 элементами = 0
Количество подматриц с 4 элементами = 1

Поскольку все записи равны 1, сумма становится равной
сумма = 1 * 4 + 2 * 4 + 3 * 0 + 4 * 1 = 16

Ввод: arr [] = {{1, 2, 3},
                 {4, 5, 6},
                 {7, 8, 9}}
Выход: 500

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Простое решение: наивное решение - сгенерировать все возможные подматрицы и просуммировать их.
Временная сложность этого подхода будет O (n ⁶ ).

Эффективное решение: для каждого элемента матрицы попробуем найти количество подматриц, в которых будет лежать этот элемент.
Это можно сделать за O (1) раз. Предположим, что индекс элемента равен (X, Y) при индексировании на основе 0, тогда количество подматриц (S _{x, y} ) для этого элемента может быть задано формулой S _{x, y} = (X + 1) * (Y + 1) * (N - X) * (N - Y) . Эта формула работает, потому что нам просто нужно выбрать две разные позиции в матрице, которые создадут подматрицу, охватывающую элемент. Таким образом, для каждого элемента «сумма» может быть обновлена как сумма + = (S _{x, y} ) * Arr _{x, y} .

Ниже представлена реализация описанного выше подхода:

Здесь нам нужно попытаться решить этот вопрос в Технике обратного поиска :

1) Для конкретного элемента каковы возможные подматрицы, в которые этот элемент будет включен .

2) Когда мы получаем количество возможных подматриц, мы можем подсчитать вклад этого конкретного элемента, выполнив (a [i] * общее количество подматриц, в которые он будет включен), где a [i] = текущий элемент

3) Теперь возникает вопрос, как найти количество возможных подматриц для конкретного элемента.

[[1 2 3]

[4 5 6]

[7 8 9]]

Итак, давайте рассмотрим текущий элемент как 5, поэтому для 5 есть (X + 1) * (Y + 1) варианты, в которых могут лежать координаты начальной точки подматрицы (вверху слева)

Точно так же будет (NX) * (NY) вариантов, в которых могут лежать конечные координаты этой подматрицы (внизу справа)

Количество вариантов для верхнего левого угла = (X + 1) * (Y + 1)

Количество вариантов для нижнего правого угла = (NX) * (NY)

Общее количество вариантов выбора для текущего элемента, который будет включен в подматрицу, будет: (X + 1) * (Y + 1) * (NX) * (NY)

Составление текущего элемента, который может быть включен во все возможные подматрицы, будет = arr [X] [Y] * (X + 1) * (Y + 1) * (NX) * (NY)

где X и Y - номера подматриц.

Сложность времени: O (N ^ 2)

Space Complexity : O(1)

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[][])
    {
        // Varialbe 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)
{
    // Varialbe 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>

Output:

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы

Сумма всех подматриц данной матрицы

C++

Java

Python3

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ