Рубрики

Максимальная сумма прямоугольника в 2D матрице | DP-27

Для данного двумерного массива найдите в нем максимальную сумму подмассива. Например, в следующем двумерном массиве подмассив с максимальной суммой выделен синим прямоугольником, а сумма этого подмассива равна 29.

Эта проблема в основном является расширением непрерывного подмассива с наибольшей суммой для одномерного массива .

Наивным решением этой проблемы является проверка каждого возможного прямоугольника в данном двумерном массиве. Это решение требует 4 вложенных цикла, и временная сложность этого решения будет O (n ^ 4).

Алгоритм Кадане для одномерного массива можно использовать для уменьшения сложности времени до O (n ^ 3). Идея состоит в том, чтобы исправить левый и правый столбцы один за другим и найти максимальную сумму смежных строк для каждой левой и правой пары столбцов. Мы в основном находим номера верхней и нижней строк (которые имеют максимальную сумму) для каждой фиксированной пары левого и правого столбцов. Чтобы найти номера верхней и нижней строки, вычислите количество элементов в каждой строке слева направо и сохраните эти суммы в массиве, скажем, temp []. Таким образом, temp [i] указывает сумму элементов слева направо в строке i. Если мы применим 1D-алгоритм Кадане к temp [] и получим максимальную сумму подмассива temp, эта максимальная сумма будет максимально возможной суммой с левыми и правыми граничными столбцами. Чтобы получить общую максимальную сумму, мы сравниваем эту сумму с максимальной суммой на данный момент.

C ++

// Программа для поиска максимальной суммы подмассива
// в заданном 2D массиве
#include<bits/stdc++.h> 

using namespace std; 

  
#define ROW 4 
#define COL 5 

  
// Реализация алгоритма Кадане для
// 1D массив. Функция возвращает максимум
// суммируем и сохраняем начальный и конечный индексы
// максимальной суммы подмассива по адресам
// указывается указателями начала и конца
// соответственно.

int kadane(int* arr, int* start,

           int* finish, int n) 

    // инициализируем сумму, maxSum и

    int sum = 0, maxSum = INT_MIN, i; 

  

    // Просто начальное значение для проверки

    // для всех отрицательных значений case

    *finish = -1; 

  

    // локальная переменная

    int local_start = 0; 

  

    for (i = 0; i < n; ++i) 

    

        sum += arr[i]; 

        if (sum < 0) 

        

            sum = 0; 

            local_start = i + 1; 

        

        else if (sum > maxSum) 

        

            maxSum = sum; 

            *start = local_start; 

            *finish = i; 

        

    

  

    // есть хотя бы один

    // неотрицательное число

    if (*finish != -1) 

        return maxSum; 

  

    // Особый случай: когда все числа

    // в arr [] отрицательны

    maxSum = arr[0]; 

    *start = *finish = 0; 

  

    // Находим максимальный элемент в массиве

    for (i = 1; i < n; i++) 

    

        if (arr[i] > maxSum) 

        

            maxSum = arr[i]; 

            *start = *finish = i; 

        

    

    return maxSum; 

  
// Основная функция, которая находит
// прямоугольник с максимальной суммой в M [] []

void findMaxSum(int M[][COL]) 

    // Переменные для хранения конечного результата

    int maxSum = INT_MIN, finalLeft, finalRight, 

                          finalTop, finalBottom; 

  

    int left, right, i; 

    int temp[ROW], sum, start, finish; 

  

    // Устанавливаем левый столбец

    for (left = 0; left < COL; ++left) 

    

        // Инициализируем все элементы temp как 0

        memset(temp, 0, sizeof(temp)); 

  

        // Установить правый столбец для левого

        // столбец, заданный внешним циклом

        for (right = left; right < COL; ++right) 

        

              

            // Рассчитать сумму между текущим левым

            // и подходит для каждой строки 'i'

            for (i = 0; i < ROW; ++i) 

                temp[i] += M[i][right]; 

  

            // Находим максимальную сумму подмассива в temp [].

            // Функция kadane () также устанавливает значения

            // начала и окончания. Таким образом, «сумма» является суммой

            // прямоугольник между (начало, слева) и

            // (финиш, справа), что является максимальной суммой

            // с граничными столбцами строго по левому краю

            // и верно.

            sum = kadane(temp, &start, &finish, ROW); 

  

            // Сравнить сумму с максимальной суммой.

            // Если сумма больше, обновите maxSum и

            // другие выходные значения

            if (sum > maxSum) 

            

                maxSum = sum; 

                finalLeft = left; 

                finalRight = right; 

                finalTop = start; 

                finalBottom = finish; 

            

        

    

  

    // Распечатать окончательные значения

    cout << "(Top, Left) (" << finalTop

         << ", " << finalLeft << ")" << endl; 

    cout << "(Bottom, Right) (" << finalBottom 

         << ", " << finalRight << ")" << endl; 

    cout << "Max sum is: " << maxSum << endl; 

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

int main() 

    int M[ROW][COL] = {{1, 2, -1, -4, -20}, 

                       {-8, -3, 4, 2, 1}, 

                       {3, 8, 10, 1, 3}, 

                       {-4, -1, 1, 7, -6}}; 

  

    findMaxSum(M); 

  

    return 0; 

  
// Этот код предоставлен
// ратбхупендра

С

// Программа для поиска максимальной суммы подмассива в данном двумерном массиве
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define ROW 4
#define COL 5

  
// Реализация алгоритма Кадане для одномерного массива. Функция
// возвращает максимальную сумму и сохраняет начальный и конечный индексы
// максимальная сумма подмассива по адресам, указанным указателями начала и конца
// соответственно.

int kadane(int* arr, int* start, int* finish, int n)

{

    // инициализируем сумму, maxSum и

    int sum = 0, maxSum = INT_MIN, i;

  

    // Просто какое-то начальное значение для проверки всех отрицательных значений case

    *finish = -1;

  

    // локальная переменная

    int local_start = 0;

  

    for (i = 0; i < n; ++i)

    {

        sum += arr[i];

        if (sum < 0)

        {

            sum = 0;

            local_start = i+1;

        }

        else if (sum > maxSum)

        {

            maxSum = sum;

            *start = local_start;

            *finish = i;

        }

    }

  

     // есть хотя бы одно неотрицательное число

    if (*finish != -1)

        return maxSum;

  

    // Особый случай: когда все числа в arr [] отрицательны

    maxSum = arr[0];

    *start = *finish = 0;

  

    // Находим максимальный элемент в массиве

    for (i = 1; i < n; i++)

    {

        if (arr[i] > maxSum)

        {

            maxSum = arr[i];

            *start = *finish = i;

        }

    }

    return maxSum;

}

  
// Основная функция, которая находит прямоугольник с максимальной суммой в M [] []

void findMaxSum(int M[][COL])

{

    // Переменные для хранения конечного результата

    int maxSum = INT_MIN, finalLeft, finalRight, finalTop, finalBottom;

  

    int left, right, i;

    int temp[ROW], sum, start, finish;

  

    // Устанавливаем левый столбец

    for (left = 0; left < COL; ++left)

    {

        // Инициализируем все элементы temp как 0

        memset(temp, 0, sizeof(temp));

  

        // Установить правый столбец для левого столбца, заданного внешним циклом

        for (right = left; right < COL; ++right)

        {

           // Вычисляем сумму между текущими слева и справа для каждой строки 'i'

            for (i = 0; i < ROW; ++i)

                temp[i] += M[i][right];

  

            // Находим максимальную сумму подмассива в temp []. Кадане ()

            // функция также устанавливает значения начала и конца. Итак, «сумма»

            // сумма прямоугольника между (начало, слева) и (конец, справа)

            // которая является максимальной суммой с граничными столбцами строго как

            // Лево и право.

            sum = kadane(temp, &start, &finish, ROW);

  

            // Сравнить сумму с максимальной суммой. Если сумма больше, то

            // обновляем maxSum и другие выходные значения

            if (sum > maxSum)

            {

                maxSum = sum;

                finalLeft = left;

                finalRight = right;

                finalTop = start;

                finalBottom = finish;

            }

        }

    }

  

    // Распечатать окончательные значения

    printf("(Top, Left) (%d, %d)\n", finalTop, finalLeft);

    printf("(Bottom, Right) (%d, %d)\n", finalBottom, finalRight);

    printf("Max sum is: %d\n", maxSum);

}

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

int main()

{

    int M[ROW][COL] = {{1, 2, -1, -4, -20},

                       {-8, -3, 4, 2, 1},

                       {3, 8, 10, 1, 3},

                       {-4, -1, 1, 7, -6}

                      };

  

    findMaxSum(M);

  

    return 0;

}

Джава

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

  

import java.util.*;

import java.lang.*;

import java.io.*;

   

class MaximumSumRectangle {

      

    // Функция для поиска максимальной суммы прямоугольника

    // подматрица

    private static int maxSumRectangle(int [][] mat) {

        int m = mat.length;

        int n = mat[0].length;

        int preSum[][] = new int[m+1][n];

   

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

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

                preSum[i+1][j] = preSum[i][j] + mat[i][j];

            }

        }

   

        int maxSum = -1;

        int minSum = Integer.MIN_VALUE;

        int negRow = 0, negCol = 0;

        int rStart = 0, rEnd = 0, cStart = 0, cEnd = 0;

        for(int rowStart = 0; rowStart < m; rowStart++) {

            for(int row = rowStart; row < m; row++){

                int sum = 0;

                int curColStart = 0;

                for(int col = 0; col < n; col++) {

                    sum += preSum[row+1][col] - preSum[rowStart][col];

                    if(sum < 0) {

                        if(minSum < sum) {

                            minSum = sum;

                            negRow = row;

                            negCol = col;

                        }

                        sum = 0;

                        curColStart = col+1;

                    }

                    else if(maxSum < sum) {

                        maxSum = sum;

                        rStart = rowStart;

                        rEnd = row;

                        cStart = curColStart;

                        cEnd = col;

                    }

                }

            }

        }

          

        // Печать окончательных значений

        if(maxSum == -1) {

            System.out.println("from row - " + negRow +

                                    " to row - " + negRow);

            System.out.println("from col - " + negCol + 

                                " to col - " + negCol);

        }

        else {

            System.out.println("from row - " + rStart + " to row - " + rEnd);

            System.out.println("from col - " + cStart + " to col - " + cEnd);

        }

        return maxSum == -1 ? minSum : maxSum;

    }

      

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

    public static void main(String[] args) {

        int arr[][] = new int[][] {{1, 2, -1, -4, -20}, 

                    {-8, -3, 4, 2, 1}, 

                    {3, 8, 10, 1, 3}, 

                    {-4, -1, 1, 7, -6}};

        System.out.println(maxSumRectangle(arr));

    }

}

  
// Этот код предоставлен Nayanava De

python3

# Python3 программа для поиска максимальной суммы
# подмассив в данном двумерном массиве

  
# Реализация алгоритма Кадане
# для 1D массива. Функция возвращает
# максимальная сумма и магазины, начиная и
# конечные индексы максимальной суммы подмассива
# по адресам, указанным в начале и в конце
# указатели соответственно.

def kadane(arr, start, finish, n):

      

    # инициализировать сумму, maxSum и

    Sum = 0

    maxSum = -999999999999

    i = None

  

    # Просто начальное значение для проверки

    # для всех отрицательных значений case

    finish[0] = -1

  

    # локальная переменная

    local_start = 0

      

    for i in range(n):

        Sum += arr[i] 

        if Sum < 0:

            Sum = 0

            local_start = i + 1

        elif Sum > maxSum:

            maxSum = Sum

            start[0] = local_start 

            finish[0] = i

  

    # Есть хотя бы один

    # неотрицательное число

    if finish[0] != -1

        return maxSum 

  

    # Особый случай: когда все числа

    # в обр [отрицательны

    maxSum = arr[0

    start[0] = finish[0] = 0

  

    # Найти максимальный элемент в массиве

    for i in range(1, n):

        if arr[i] > maxSum:

            maxSum = arr[i] 

            start[0] = finish[0] = i

    return maxSum

  
# Основная функция, которая находит максимум
# сумма прямоугольника в M [] []

def findMaxSum(M):

    global ROW, COL

      

    # Переменные для хранения конечного результата

    maxSum, finalLeft = -999999999999, None

    finalRight, finalTop, finalBottom = None, None, None

    left, right, i = None, None, None

      

    temp = [None] * ROW

    Sum = 0

    start = [0]

    finish = [0

  

    # Установите левый столбец

    for left in range(COL):

          

        # Инициализировать все элементы temp как 0

        temp = [0] * ROW 

  

        # Установите правую колонку для левой

        # столбец, установленный внешним циклом

        for right in range(left, COL):

              

            # Рассчитать сумму между текущим левым

            # и справа для каждой строки 'i'

            for i in range(ROW):

                temp[i] += M[i][right] 

  

            # Найти максимальную сумму подмассива в

            # temp []. Функция kadane () также

            # устанавливает значения начала и конца.

            # Таким образом, «сумма» является суммой прямоугольника между

            # (начало слева) и (конец справа), которые

            # - максимальная сумма с граничными столбцами

            # строго как слева и справа.

            Sum = kadane(temp, start, finish, ROW) 

  

            # Сравните сумму с максимальной суммой до сих пор.

            # Если сумма больше, обновите maxSum

            # и другие выходные значения

            if Sum > maxSum:

                maxSum = Sum

                finalLeft = left 

                finalRight = right 

                finalTop = start[0

                finalBottom = finish[0]

  

    # Прфинальные значения

    print("(Top, Left)", "(", finalTop, 

                              finalLeft, ")"

    print("(Bottom, Right)", "(", finalBottom, 

                                  finalRight, ")"

    print("Max sum is:", maxSum)

  
Код водителя

ROW = 4

COL = 5

M = [[1, 2, -1, -4, -20],

     [-8, -3, 4, 2, 1], 

     [3, 8, 10, 1, 3], 

     [-4, -1, 1, 7, -6]] 

  
findMaxSum(M)

  
# Этот код предоставлен PranchalK

C #

// C # По заданному 2D массиву найти
// максимальная сумма подмассива в нем

using System;

  

class GFG 

  
/ **
* Найти maxSum в массиве 1d
*
* return {maxSum, left, right}
* /

public static int[] kadane(int[] a)

    int[] result = new int[]{int.MinValue, 0, -1}; 

    int currentSum = 0; 

    int localStart = 0; 

  

    for (int i = 0; i < a.Length; i++) 

    

        currentSum += a[i]; 

        if (currentSum < 0) 

        

            currentSum = 0; 

            localStart = i + 1; 

        

        else if (currentSum > result[0]) 

        

            result[0] = currentSum; 

            result[1] = localStart; 

            result[2] = i; 

        

    

      

    // все числа в являются отрицательными

    if (result[2] == -1) 

    

        result[0] = 0; 

        for (int i = 0; i < a.Length; i++) 

        

            if (a[i] > result[0]) 

            

                result[0] = a[i]; 

                result[1] = i; 

                result[2] = i; 

            

        

    

    return result; 

  
/ **
* Чтобы найти и напечатать maxSum,

 (слева вверху), (справа внизу)

* /

public static void findMaxSubMatrix(int [,]a) 

    int cols = a.GetLength(1);

    int rows = a.GetLength(0); 

    int[] currentResult; 

    int maxSum = int.MinValue; 

    int left = 0; 

    int top = 0; 

    int right = 0; 

    int bottom = 0; 

      

    for (int leftCol = 0; 

             leftCol < cols; leftCol++)

    

        int[] tmp = new int[rows]; 

  

        for (int rightCol = leftCol; 

                 rightCol < cols; rightCol++) 

        

      

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

            

                tmp[i] += a[i,rightCol]; 

            

            currentResult = kadane(tmp); 

            if (currentResult[0] > maxSum) 

            

                maxSum = currentResult[0]; 

                left = leftCol; 

                top = currentResult[1]; 

                right = rightCol; 

                bottom = currentResult[2]; 

            

        

    

      

    Console.Write("MaxSum: " + maxSum + 

            ", range: [(" + left + ", " + top + 

            ")(" + right + ", " + bottom + ")]"); 

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

public static void Main ()

    int [,]arr = { {1, 2, -1, -4, -20}, 

                   {-8, -3, 4, 2, 1}, 

                   {3, 8, 10, 1, 3}, 

                   {-4, -1, 1, 7, -6} }; 

    findMaxSubMatrix(arr);


  
// Этот код добавлен
// by PrinciRaj1992


Выход:

(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
Max sum is: 29

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

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

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

Максимальная сумма прямоугольника в 2D матрице | DP-27

0.00 (0%) 0 votes