Rectángulo de suma máxima en una array 2D | DP-27

Dado un arreglo 2D, encuentre el subarreglo de suma máxima en él. Por ejemplo, en la siguiente array 2D, el subarreglo de suma máxima se resalta con un rectángulo azul y la suma de este subarreglo es 29.

Este problema es principalmente una extensión del subarreglo contiguo de suma más grande para un arreglo 1D .  

La solución ingenua para este problema es verificar todos los rectángulos posibles en la array 2D dada. Esta solución requiere 6 bucles anidados:  

  • 4 para la coordenada inicial y final de los 2 ejes O(n 4 )
  • y 2 para la sumatoria de la subarray O(n 2 ).

La complejidad temporal total de esta solución sería O(n 6 ).

Enfoque eficiente – 

El algoritmo de Kadane para array 1D se puede usar para reducir la complejidad del tiempo a O (n ^ 3). La idea es arreglar las columnas izquierda y derecha una por una y encontrar la suma máxima de filas contiguas para cada par de columnas izquierda y derecha. Básicamente, encontramos números de fila superior e inferior (que tienen una suma máxima) para cada par de columnas fijas izquierda y derecha. Para encontrar los números de las filas superior e inferior, calcule la suma de los elementos en cada fila de izquierda a derecha y almacene estas sumas en una array, digamos temp[]. Entonces temp[i] indica la suma de los elementos de izquierda a derecha en la fila i. Si aplicamos el algoritmo 1D de Kadane en temp[] y obtenemos el subarreglo de suma máxima de temp, esta suma máxima sería la suma máxima posible con izquierda y derecha como columnas límite. Para obtener la suma máxima general, comparamos esta suma con la suma máxima hasta el momento.

Implementación:

C++

// Program to find maximum sum subarray
// in a given 2D array
#include <bits/stdc++.h>
using namespace std;
 
#define ROW 4
#define COL 5
 
// Implementation of Kadane's algorithm for
// 1D array. The function returns the maximum
// sum and stores starting and ending indexes
// of the maximum sum subarray at addresses
// pointed by start and finish pointers
// respectively.
int kadane(int* arr, int* start, int* finish, int n)
{
    // initialize sum, maxSum and
    int sum = 0, maxSum = INT_MIN, i;
 
    // Just some initial value to check
    // for all negative values case
    *finish = -1;
 
    // local variable
    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;
        }
    }
 
    // There is at-least one
    // non-negative number
    if (*finish != -1)
        return maxSum;
 
    // Special Case: When all numbers
    // in arr[] are negative
    maxSum = arr[0];
    *start = *finish = 0;
 
    // Find the maximum element in array
    for (i = 1; i < n; i++)
    {
        if (arr[i] > maxSum)
        {
            maxSum = arr[i];
            *start = *finish = i;
        }
    }
    return maxSum;
}
 
// The main function that finds
// maximum sum rectangle in M[][]
void findMaxSum(int M[][COL])
{
    // Variables to store the final output
    int maxSum = INT_MIN,
                 finalLeft,
                 finalRight,
                 finalTop,
                 finalBottom;
 
    int left, right, i;
    int temp[ROW], sum, start, finish;
 
    // Set the left column
    for (left = 0; left < COL; ++left) {
        // Initialize all elements of temp as 0
        memset(temp, 0, sizeof(temp));
 
        // Set the right column for the left
        // column set by outer loop
        for (right = left; right < COL; ++right) {
 
            // Calculate sum between current left
            // and right for every row 'i'
            for (i = 0; i < ROW; ++i)
                temp[i] += M[i][right];
 
            // Find the maximum sum subarray in temp[].
            // The kadane() function also sets values
            // of start and finish. So 'sum' is sum of
            // rectangle between (start, left) and
            // (finish, right) which is the maximum sum
            // with boundary columns strictly as left
            // and right.
            sum = kadane(temp, &start, &finish, ROW);
 
            // Compare sum with maximum sum so far.
            // If sum is more, then update maxSum and
            // other output values
            if (sum > maxSum) {
                maxSum = sum;
                finalLeft = left;
                finalRight = right;
                finalTop = start;
                finalBottom = finish;
            }
        }
    }
 
    // Print final values
    cout << "(Top, Left) ("
         << finalTop << ", "
         << finalLeft
         << ")" << endl;
    cout << "(Bottom, Right) ("
         << finalBottom << ", "
         << finalRight << ")" << endl;
    cout << "Max sum is: " << maxSum << endl;
}
 
// Driver Code
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 } };
 
    // Function call
    findMaxSum(M);
 
    return 0;
}
 
// This code is contributed by
// rathbhupendra

C

// Program to find maximum sum subarray
// in a given 2D array
#include <limits.h>
#include <stdio.h>
#include <string.h>
#define ROW 4
#define COL 5
 
// Implementation of Kadane's algorithm
// for 1D array. The function returns the
// maximum sum and stores starting and
// ending indexes of the maximum sum subarray
// at addresses pointed by start and finish
// pointers respectively.
int kadane(int* arr, int* start,
           int* finish, int n)
{
    // initialize sum, maxSum and
    int sum = 0, maxSum = INT_MIN, i;
 
    // Just some initial value to check for all negative
    // values case
    *finish = -1;
 
    // local variable
    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;
        }
    }
 
    // There is at-least one non-negative number
    if (*finish != -1)
        return maxSum;
 
    // Special Case: When all numbers in arr[]
    // are negative
    maxSum = arr[0];
    *start = *finish = 0;
 
    // Find the maximum element in array
    for (i = 1; i < n; i++)
    {
        if (arr[i] > maxSum)
        {
            maxSum = arr[i];
            *start = *finish = i;
        }
    }
    return maxSum;
}
 
// The main function that finds maximum
// sum rectangle in
// M[][]
void findMaxSum(int M[][COL])
{
    // Variables to store the final output
    int maxSum = INT_MIN,
                 finalLeft,
                 finalRight,
                 finalTop,
                 finalBottom;
 
    int left, right, i;
    int temp[ROW], sum, start, finish;
 
    // Set the left column
    for (left = 0; left < COL; ++left)
    {
        // Initialize all elements of temp as 0
        memset(temp, 0, sizeof(temp));
 
        // Set the right column for the left column set by
        // outer loop
        for (right = left; right < COL; ++right) {
            // Calculate sum between current left and right
            // for every row 'i'
            for (i = 0; i < ROW; ++i)
                temp[i] += M[i][right];
 
            // Find the maximum sum subarray in temp[].
            // The kadane() function also sets values of
            // start and finish.  So 'sum' is sum of
            // rectangle between (start, left) and (finish,
            //  right) which is the maximum sum with boundary
            //  columns strictly as left and right.
            sum = kadane(temp, &start, &finish, ROW);
 
            // Compare sum with maximum sum so far. If sum
            // is more, then update maxSum and other output
            // values
            if (sum > maxSum)
            {
                maxSum = sum;
                finalLeft = left;
                finalRight = right;
                finalTop = start;
                finalBottom = finish;
            }
        }
    }
 
    // Print final values
    printf("(Top, Left) (%d, %d)\n", finalTop, finalLeft);
    printf("(Bottom, Right) (%d, %d)\n", finalBottom,
           finalRight);
    printf("Max sum is: %d\n", maxSum);
}
 
// Driver Code
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 } };
 
    // Function call
    findMaxSum(M);
 
    return 0;
}

Java

// Java Program to find max sum rectangular submatrix
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
class MaximumSumRectangle
{
 
    // Function to find maximum sum rectangular
    // submatrix
    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;
                    }
                }
            }
        }
 
        // Printing final values
        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;
    }
 
    // Driver Code
    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 } };
       
        // Function call
        System.out.println(maxSumRectangle(arr));
    }
}
 
// This code is contributed by Nayanava De

Python3

# Python3 program to find maximum sum
# subarray in a given 2D array
 
# Implementation of Kadane's algorithm
# for 1D array. The function returns the
# maximum sum and stores starting and
# ending indexes of the maximum sum subarray
# at addresses pointed by start and finish
# pointers respectively.
 
 
def kadane(arr, start, finish, n):
 
    # initialize sum, maxSum and
    Sum = 0
    maxSum = -999999999999
    i = None
 
    # Just some initial value to check
    # for all negative values case
    finish[0] = -1
 
    # local variable
    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
 
    # There is at-least one
    # non-negative number
    if finish[0] != -1:
        return maxSum
 
    # Special Case: When all numbers
    # in arr[] are negative
    maxSum = arr[0]
    start[0] = finish[0] = 0
 
    # Find the maximum element in array
    for i in range(1, n):
        if arr[i] > maxSum:
            maxSum = arr[i]
            start[0] = finish[0] = i
    return maxSum
 
# The main function that finds maximum
# sum rectangle in M[][]
 
 
def findMaxSum(M):
    global ROW, COL
 
    # Variables to store the final output
    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]
 
    # Set the left column
    for left in range(COL):
 
        # Initialize all elements of temp as 0
        temp = [0] * ROW
 
        # Set the right column for the left
        # column set by outer loop
        for right in range(left, COL):
 
            # Calculate sum between current left
            # and right for every row 'i'
            for i in range(ROW):
                temp[i] += M[i][right]
 
            # Find the maximum sum subarray in
            # temp[]. The kadane() function also
            # sets values of start and finish.
            # So 'sum' is sum of rectangle between
            # (start, left) and (finish, right) which
            # is the maximum sum with boundary columns
            # strictly as left and right.
            Sum = kadane(temp, start, finish, ROW)
 
            # Compare sum with maximum sum so far.
            # If sum is more, then update maxSum
            # and other output values
            if Sum > maxSum:
                maxSum = Sum
                finalLeft = left
                finalRight = right
                finalTop = start[0]
                finalBottom = finish[0]
 
    # Prfinal values
    print("(Top, Left)", "(", finalTop,
          finalLeft, ")")
    print("(Bottom, Right)", "(", finalBottom,
          finalRight, ")")
    print("Max sum is:", maxSum)
 
 
# Driver Code
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]]
 
# Function call
findMaxSum(M)
 
# This code is contributed by PranchalK

C#

// C# Given a 2D array, find the
// maximum sum subarray in it
using System;
 
class GFG {
 
    /**
     * To find maxSum in 1d array
     *
     * 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;
            }
        }
 
        // all numbers in a are negative
        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;
    }
 
    /**
    * To find and print maxSum,
     (left, top),(right, bottom)
    */
    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 + ")]");
    }
 
    // Driver Code
    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 } };
       
        // Function call
        findMaxSubMatrix(arr);
    }
}
 
// This code is contributed
// by PrinciRaj1992

Javascript

<script>
 
// Program to find maximum sum subarray
// in a given 2D array
 
var ROW = 4
var COL = 5
var start = 0
var finish = 0
 
// Implementation of Kadane's algorithm for
// 1D array. The function returns the maximum
// sum and stores starting and ending indexes
// of the maximum sum subarray at addresses
// pointed by start and finish pointers
// respectively.
function kadane(arr, n)
{
    // initialize sum, maxSum and
    var sum = 0, maxSum = -1000000000, i;
 
    // Just some initial value to check
    // for all negative values case
    finish = -1;
 
    // local variable
    var 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;
        }
    }
 
    // There is at-least one
    // non-negative number
    if (finish != -1)
        return maxSum;
 
    // Special Case: When all numbers
    // in arr[] are negative
    maxSum = arr[0];
    start = finish = 0;
 
    // Find the maximum element in array
    for (i = 1; i < n; i++)
    {
        if (arr[i] > maxSum)
        {
            maxSum = arr[i];
            start = finish = i;
        }
    }
    return maxSum;
}
 
// The main function that finds
// maximum sum rectangle in M[][]
function findMaxSum(M)
{
    // Variables to store the final output
    var maxSum = -1000000000,
                 finalLeft=0,
                 finalRight=0,
                 finalTop=0,
                 finalBottom=0;
 
    var left, right, i;
    var temp = Array(ROW);
    var sum;
 
    // Set the left column
    for (left = 0; left < COL; ++left) {
        // Initialize all elements of temp as 0
        temp = Array(ROW).fill(0);
 
        // Set the right column for the left
        // column set by outer loop
        for (right = left; right < COL; ++right) {
 
            // Calculate sum between current left
            // and right for every row 'i'
            for (i = 0; i < ROW; ++i)
                temp[i] += M[i][right];
 
            // Find the maximum sum subarray in temp[].
            // The kadane() function also sets values
            // of start and finish. So 'sum' is sum of
            // rectangle between (start, left) and
            // (finish, right) which is the maximum sum
            // with boundary columns strictly as left
            // and right.
            sum = kadane(temp, ROW);
 
            // Compare sum with maximum sum so far.
            // If sum is more, then update maxSum and
            // other output values
            if (sum > maxSum) {
                maxSum = sum;
                finalLeft = left;
                finalRight = right;
                finalTop = start;
                finalBottom = finish;
            }
        }
    }
 
    // Print final values
    document.write("(Top, Left) ("
         + finalTop + ", "
         + finalLeft
         + ")" + "<br>");
    document.write("(Bottom, Right) ("
         + finalBottom + ", "
         + finalRight + ")" + "<br>");
    document.write("Max sum is: " + maxSum + "<br>");
}
 
// Driver Code
var M = [ [ 1, 2, -1, -4, -20 ],
                    [ -8, -3, 4, 2, 1 ],
                    [ 3, 8, 10, 1, 3 ],
                    [ -4, -1, 1, 7, -6 ] ];
// Function call
findMaxSum(M);
 
// This code is contributed by rutvik_56.
</script>
Producción

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

Complejidad de tiempo: O(c*c*r), donde c representa el número de columnas y r representa el número de filas en la array dada.
Espacio Auxiliar: O(r), donde r representa el número de filas en la array dada.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *