Рубрики

Вывести максимальную сумму квадратной подматрицы заданного размера

Для данной матрицы N x N найдите подматрицу akxk, где k <= N и k> = 1, чтобы сумма всех элементов в подматрице была максимальной. Входная матрица может содержать ноль, положительные и отрицательные числа.

Например, рассмотрим матрицу ниже, если k = 3, то выходные данные должны вывести подматрицу, заключенную в синий цвет.

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Простое решение состоит в том, чтобы рассмотреть все возможные подобласти размера kxk в нашей входной матрице и найти тот, который имеет максимальную сумму. Временная сложность вышеуказанного решения составляет O (N 2 k 2 ).

Мы можем решить эту проблему за O (N 2 ) время. Эта проблема в основном является расширением этой проблемы печати всех сумм. Идея состоит в том, чтобы предварительно обработать данную квадратную матрицу. На этапе предварительной обработки вычислите сумму всех вертикальных полос размером kx 1 во временной квадратной матрице stripSum [] []. Как только у нас есть сумма всех вертикальных полос, мы можем вычислить сумму первого квадрата в строке как сумму первых k полос в этом ряду, а для оставшихся суб квадратов мы можем вычислить сумму за время O (1), удалив крайняя левая полоса предыдущего квадрата и добавление самой правой полосы нового квадрата.
Ниже приведена реализация вышеуказанной идеи.

C ++

// Эффективная программа на C ++ для поиска максимальной суммы
// матрица субквадрат
#include <bits/stdc++.h>

using namespace std;

  
// Размер данной матрицы
#define N 5

  
// AO (n ^ 2) функция до максимальной суммы
// квадраты размером kxk в данном квадрате
// матрица размером nxn

void printMaxSumSub(int mat[][N], int k)

{

    // k должно быть меньше или равно n

    if (k > N) return;

  

    // 1: предварительная обработка

    // Для хранения сумм всех полос размером kx 1

    int stripSum[N][N];

  

    // Перейти столбец за столбцом

    for (int j=0; j<N; j++)

    {

        // Вычисляем сумму первого прямоугольника kx 1

        // в этом столбце

        int sum = 0;

        for (int i=0; i<k; i++)

            sum += mat[i][j];

        stripSum[0][j] = sum;

  

        // Рассчитать сумму оставшихся прямоугольников

        for (int i=1; i<N-k+1; i++)

        {

            sum += (mat[i+k-1][j] - mat[i-1][j]);

            stripSum[i][j] = sum;

        }

    }

  

    // max_sum хранит максимальную сумму и ее

    // позиция в матрице

    int max_sum = INT_MIN, *pos = NULL;

  

    // 2: РАСЧЕТНАЯ СУММА субквадрат с использованием stripSum [] []

    for (int i=0; i<N-k+1; i++)

    {

        // Вычисляем и печатаем сумму первого квадрата

        // в этой строке

        int sum = 0;

        for (int j = 0; j<k; j++)

            sum += stripSum[i][j];

  

        // Обновляем max_sum и позицию результата

        if (sum > max_sum)

        {

            max_sum = sum;

            pos = &(mat[i][0]);

        }

  

        // Рассчитать сумму оставшихся квадратов в

        // текущая строка путем удаления самой левой

        // полоса предыдущего квадрата и добавление

        // новая полоса

        for (int j=1; j<N-k+1; j++)

        {

            sum += (stripSum[i][j+k-1] - stripSum[i][j-1]);

  

            // Обновляем max_sum и позицию результата

            if (sum > max_sum)

            {

                max_sum = sum;

                pos = &(mat[i][j]);

            }

        }

    }

  

    // Распечатать матрицу результатов

    for (int i=0; i<k; i++)

    {

        for (int j=0; j<k; j++)

            cout << *(pos + i*N + j) << " ";

        cout << endl;

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int mat[N][N] = {{1, 1, 1, 1, 1},

        {2, 2, 2, 2, 2},

        {3, 8, 6, 7, 3},

        {4, 4, 4, 4, 4},

        {5, 5, 5, 5, 5},

    };

    int k = 3;

   

    cout << "Maximum sum 3 x 3 matrix is\n";

    printMaxSumSub(mat, k);

  

    return 0;

}

Джава

// Эффективная Java-программа для поиска максимальной суммы
// матрица субквадрат

  
// Класс для хранения позиции начала
// максимальная сумма в матрице

class Position {

    int x;

    int y;

  

    // Конструктор

    Position(int x, int y) {

        this.x = x;

        this.y = y;

    }

  

    // Обновляет позицию, если новая максимальная сумма

    // находится

    void updatePosition(int x, int y) {

        this.x = x;

        this.y = y;

    }

  

    // возвращает текущее значение X

    int getXPosition() {

        return this.x;

    }

  

    // возвращает текущее значение y

    int getYPosition() {

        return this.y;

    }

}

  

class Gfg {

    // Размер данной матрицы

    static int N;

  

    // AO (n ^ 2) функция до максимальной суммы

    // квадраты размером kxk в данном квадрате

    // матрица размером nxn

    static void printMaxSumSub(int[][] mat, int k) {

  

        // k должно быть меньше или равно n

        if (k > N)

            return;

  

        // 1: предварительная обработка

        // Для хранения сумм всех полос размером kx 1

        int[][] stripSum = new int[N][N];

  

        // Перейти столбец за столбцом

        for (int j = 0; j < N; j++) {

  

            // Вычисляем сумму первого прямоугольника kx 1

            // в этом столбце

            int sum = 0;

            for (int i = 0; i < k; i++)

                sum += mat[i][j];

            stripSum[0][j] = sum;

  

            // Рассчитать сумму оставшихся прямоугольников

            for (int i = 1; i < N - k + 1; i++) {

                sum += (mat[i + k - 1][j] - mat[i - 1][j]);

                stripSum[i][j] = sum;

            }

        }

  

        // max_sum хранит максимальную сумму и ее

        // позиция в матрице

        int max_sum = Integer.MIN_VALUE;

        Position pos = new Position(-1, -1);

  

        // 2: РАСЧЕТНАЯ СУММА субквадрат с использованием stripSum [] []

        for (int i = 0; i < N - k + 1; i++) {

  

            // Вычисляем и печатаем сумму первого квадрата

            // в этой строке

            int sum = 0;

            for (int j = 0; j < k; j++)

                sum += stripSum[i][j];

  

            // Обновляем max_sum и позицию результата

            if (sum > max_sum) {

                max_sum = sum;

                pos.updatePosition(i, 0);

            }

  

            // Рассчитать сумму оставшихся квадратов в

            // текущая строка путем удаления самой левой

            // полоса предыдущего квадрата и добавление

            // новая полоса

            for (int j = 1; j < N - k + 1; j++) {

                sum += (stripSum[i][j + k - 1] - stripSum[i][j - 1]);

  

                // Обновляем max_sum и позицию результата

                if (sum > max_sum) {

                    max_sum = sum;

                    pos.updatePosition(i, j);

                }

            }

        }

  

        // Распечатать матрицу результатов

        for (int i = 0; i < k; i++) {

            for (int j = 0; j < k; j++) {

                System.out.print(mat[i + pos.getXPosition()][j + pos.getYPosition()] + " ");

            }

            System.out.println();

        }

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args) {

        N = 5;

        int[][] mat = { { 1, 1, 1, 1, 1 }, 

                { 2, 2, 2, 2, 2 }, 

                { 3, 8, 6, 7, 3 }, 

                { 4, 4, 4, 4, 4 },

            { 5, 5, 5, 5, 5 } };

    int k = 3;

  

        System.out.println("Maximum sum 3 x 3 matrix is");

        printMaxSumSub(mat, k);

    }

}

  
// Этот код предоставлен Вивеком Кумаром Сингхом

C #

// Эффективная программа на C # для поиска максимальной суммы
// матрица субквадрат

using System;

  
// Класс для хранения позиции начала
// максимальная сумма в матрице

class Position 

    int x; 

    int y; 

  

    // Конструктор

    public Position(int x, int y)

    

        this.x = x; 

        this.y = y; 

    

  

    // Обновляет позицию, если новая максимальная сумма

    // находится

    public void updatePosition(int x, int y)

    

        this.x = x; 

        this.y = y; 

    

  

    // возвращает текущее значение X

    public int getXPosition()

    

        return this.x; 

    

  

    // возвращает текущее значение y

    public int getYPosition() 

    

        return this.y; 

    

  

class GFG 

      

    // Размер данной матрицы

    static int N; 

  

    // AO (n ^ 2) функция до максимальной суммы

    // квадраты размером kxk в данном квадрате

    // матрица размером nxn

    static void printMaxSumSub(int[,] mat, int k) 

    

  

        // k должно быть меньше или равно n

        if (k > N) 

            return

  

        // 1: предварительная обработка

        // Для хранения сумм всех полос размером kx 1

        int[,] stripSum = new int[N, N]; 

  

        // Перейти столбец за столбцом

        for (int j = 0; j < N; j++) 

        

  

            // Вычисляем сумму первого прямоугольника kx 1

            // в этом столбце

            int sum = 0; 

            for (int i = 0; i < k; i++) 

                sum += mat[i, j]; 

            stripSum[0, j] = sum; 

  

            // Рассчитать сумму оставшихся прямоугольников

            for (int i = 1; i < N - k + 1; i++) 

            

                sum += (mat[i + k - 1, j] - 

                        mat[i - 1, j]); 

                stripSum[i, j] = sum; 

            

        

  

        // max_sum хранит максимальную сумму и ее

        // позиция в матрице

        int max_sum = int.MinValue; 

        Position pos = new Position(-1, -1); 

  

        // 2: РАСЧЕТНАЯ СУММА субквадрат с использованием stripSum [,]

        for (int i = 0; i < N - k + 1; i++)

        

  

            // Вычисляем и печатаем сумму первого квадрата

            // в этой строке

            int sum = 0; 

            for (int j = 0; j < k; j++) 

                sum += stripSum[i, j]; 

  

            // Обновляем max_sum и позицию результата

            if (sum > max_sum) 

            

                max_sum = sum; 

                pos.updatePosition(i, 0); 

            

  

            // Рассчитать сумму оставшихся квадратов в

            // текущая строка путем удаления самой левой

            // полоса предыдущего квадрата и добавление

            // новая полоса

            for (int j = 1; j < N - k + 1; j++) 

            

                sum += (stripSum[i, j + k - 1] - 

                        stripSum[i, j - 1]); 

  

                // Обновляем max_sum и позицию результата

                if (sum > max_sum)

                

                    max_sum = sum; 

                    pos.updatePosition(i, j); 

                

            

        

  

        // Распечатать матрицу результатов

        for (int i = 0; i < k; i++) 

        

            for (int j = 0; j < k; j++) 

            

                Console.Write(mat[i + pos.getXPosition(),

                                  j + pos.getYPosition()] + " "); 

            

            Console.WriteLine(); 

        

    

  

    // Код драйвера

    public static void Main(String[] args) 

    

        N = 5; 

        int[,] mat = {{ 1, 1, 1, 1, 1 }, 

                      { 2, 2, 2, 2, 2 }, 

                        { 3, 8, 6, 7, 3 }, 

                      { 4, 4, 4, 4, 4 }, 

                      { 5, 5, 5, 5, 5 }}; 

        int k = 3; 

  

        Console.WriteLine("Maximum sum 3 x 3 matrix is"); 

        printMaxSumSub(mat, k); 

    

  
// Этот код предоставлен Принчи Сингхом

Выход:

Maximum sum 3 x 3 matrix is
8 6 7
4 4 4
5 5 5

Статьи по Теме:
По заданной квадратной матрице nxn найдите сумму всех квадратов размера kxk.
Максимальная сумма прямоугольника в 2D матрице

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Вывести максимальную сумму квадратной подматрицы заданного размера

0.00 (0%) 0 votes