Рубрики

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

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

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

// Программа для поиска максимальной суммы подмассива в данном двумерном массиве
#include <limits.h>
#include <stdio.h>
#include <string.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;

}

Выход:

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

Пожалуйста, обратитесь к полной статье о максимальной сумме прямоугольника в 2D матрице | DP-27 для более подробной информации!

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

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

0.00 (0%) 0 votes