Dada una array mat[][] de dimensiones N * M , y un número entero K , la tarea es encontrar la suma máxima de cualquier rectángulo posible de la array dada, cuya suma de elementos es como máximo K .
Ejemplos:
Entrada: mat[][] ={{1, 0, 1}, {0, -2, 3}}, K = 2
Salida: 2
Explicación: La suma máxima posible en cualquier rectángulo de la array es 2 (<= K), obtenido de la array {{0, 1}, {-2, 3}}.Entrada: mat[][] = {{2, 2, -1}}, K = 3
Salida: 3
Explicación: El rectángulo de suma máxima es {{2, 2, -1}} es 3 ( <- K).
Enfoque ingenuo: el enfoque más simple es verificar todas las subarrays posibles de la array dada, ya sea que la suma de sus elementos sea como máximo K o no. Si se encuentra que es cierto, almacene la suma de esa subarray. Finalmente, imprima la suma máxima de dichas subarrays obtenidas.
Complejidad de Tiempo: O(N 6 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando un enfoque similar a encontrar el rectángulo de suma máxima en una array 2D . La única diferencia es que la suma del rectángulo no debe exceder K . La idea es arreglar las columnas izquierda y derecha una por una y en cada iteración, almacenar la suma de cada fila en el rectángulo actual y encontrar la suma máxima de subarreglo menor que K en este arreglo. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res , que almacene la suma máxima de elementos de la subarray que tenga suma como máximo K .
- Iterar sobre el rango [0, M – 1] usando la variable i para la columna izquierda y realizar los siguientes pasos:
- Inicialice una array V[] de tamaño N para almacenar la suma de elementos de cada fila entre el par de columnas izquierda y derecha.
- Iterar sobre el rango [0, M – 1] usando una variable j para la columna derecha y realizar los siguientes pasos:
- Encuentre la suma entre la columna izquierda y derecha actual de cada fila y actualice la suma en la array V[] .
- Encuentre el subarreglo de suma máxima con una suma menor que K en V[] y almacene el resultado en ans .
- Si el valor de ans es mayor que el valor de res , actualice res a ans .
- Después de completar los pasos anteriores, imprima el valor de res como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum possible
// sum of arectangle which is less than K
int maxSubarraySum(vector<int>& sum,
int k, int row)
{
int curSum = 0, curMax = INT_MIN;
// Stores the values (cum_sum - K)
set<int> sumSet;
// Insert 0 into the set sumSet
sumSet.insert(0);
// Traverse over the rows
for (int r = 0; r < row; ++r) {
// Get cumulative sum from [0 to i]
curSum += sum[r];
// Search for upperbound of
// (cSum - K) in the hashmap
auto it = sumSet.lower_bound(curSum - k);
// If upper_bound of (cSum - K)
// exists, then update max sum
if (it != sumSet.end()) {
curMax = max(curMax,
curSum - *it);
}
// Insert cumulative value
// in the hashmap
sumSet.insert(curSum);
}
// Return the maximum sum
// which is less than K
return curMax;
}
// Function to find the maximum sum of
// rectangle such that its sum is no
// larger than K
void maxSumSubmatrix(
vector<vector<int> >& matrix, int k)
{
// Stores the number of rows
// and columns
int row = matrix.size();
int col = matrix[0].size();
// Store the required result
int ret = INT_MIN;
// Set the left column
for (int i = 0; i < col; ++i) {
vector<int> sum(row, 0);
// Set the right column for the
// left column set by outer loop
for (int j = i; j < col; ++j) {
// Calculate sum between the
// current left and right
// for every row
for (int r = 0; r < row; ++r) {
sum[r] += matrix[r][j];
}
// Stores the sum of rectangle
int curMax = maxSubarraySum(
sum, k, row);
// Update the overall maximum sum
ret = max(ret, curMax);
}
}
// Print the result
cout << ret;
}
// Driver Code
int main()
{
vector<vector<int> > matrix
= { { 1, 0, 1 }, { 0, -2, 3 } };
int K = 2;
// Function Call
maxSumSubmatrix(matrix, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the maximum possible
// sum of arectangle which is less than K
static int maxSubarraySum(int[] sum,
int k, int row) {
int curSum = 0, curMax = Integer.MIN_VALUE;
// Stores the values (cum_sum - K)
Set<Integer> sumSet = new HashSet<Integer>();
// Insert 0 into the set sumSet
sumSet.add(0);
// Traverse over the rows
for (int r = 0; r < row; ++r) {
// Get cumulative sum from [0 to i]
curSum += sum[r];
// Search for upperbound of
// (cSum - K) in the hashmap
ArrayList<Integer> list = new ArrayList<Integer>();
list.addAll(sumSet);
int it = Integer.MIN_VALUE;
for (int e : list)
if (e >= (curSum - k)) {
it = e;
break;
}
// If upper_bound of (cSum - K)
// exists, then update max sum
if (it != Integer.MIN_VALUE) {
curMax = Math.max(curMax,
curSum - it);
}
// Insert cumulative value
// in the hashmap
sumSet.add(curSum);
}
// Return the maximum sum
// which is less than K
return curMax;
}
// Function to find the maximum sum of
// rectangle such that its sum is no
// larger than K
static void maxSumSubmatrix(int[][] matrix, int k) {
// Stores the number of rows
// and columns
int row = matrix.length;
int col = matrix[0].length;
// Store the required result
int ret = Integer.MIN_VALUE;
// Set the left column
for (int i = 0; i < col; ++i) {
int[] sum = new int[row];
// Set the right column for the
// left column set by outer loop
for (int j = i; j < col; ++j) {
// Calculate sum between the
// current left and right
// for every row
for (int r = 0; r < row; ++r) {
sum[r] += matrix[r][j];
}
// Stores the sum of rectangle
int curMax = maxSubarraySum(
sum, k, row);
// Update the overall maximum sum
ret = Math.max(ret, curMax);
}
}
// Print the result
System.out.print(ret);
}
// Driver Code
public static void main (String[] args) {
int[][] matrix = { { 5, -4, -3, 4 },
{ -3, -4, 4, 5 },
{5, 1, 5, -4}
};
int K = 8;
// Function Call
maxSumSubmatrix(matrix, K);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program for the above approach
from bisect import bisect_left, bisect_right
import sys
# Function to find the maximum possible
# sum of arectangle which is less than K
def maxSubarraySum(sum, k, row):
curSum, curMax = 0, -sys.maxsize - 1
# Stores the values (cum_sum - K)
sumSet = {}
# Insert 0 into the set sumSet
sumSet[0] = 1
# Traverse over the rows
for r in range(row):
# Get cumulative sum from [0 to i]
curSum += sum[r]
# Search for upperbound of
# (cSum - K) in the hashmap
arr = list(sumSet.keys())
it = bisect_left(arr, curSum - k)
# If upper_bound of (cSum - K)
# exists, then update max sum
if (it != len(arr)):
curMax = max(curMax, curSum - it)
# Insert cumulative value
# in the hashmap
sumSet[curSum] = 1
# Return the maximum sum
# which is less than K
return curMax
# Function to find the maximum sum of
# rectangle such that its sum is no
# larger than K
def maxSumSubmatrix(matrix, k):
# Stores the number of rows
# and columns
row = len(matrix)
col = len(matrix[0])
# Store the required result
ret = -sys.maxsize - 1
# Set the left column
for i in range(col):
sum = [0] * (row)
# Set the right column for the
# left column set by outer loop
for j in range(i, col):
# Calculate sum between the
# current left and right
# for every row
for r in range(row):
sum[r] += matrix[r][j]
# Stores the sum of rectangle
curMax = maxSubarraySum(sum, k, row)
# Update the overall maximum sum
ret = max(ret, curMax)
# Print the result
print(ret)
# Driver Code
if __name__ == '__main__':
matrix = [ [ 1, 0, 1 ], [ 0, -2, 3 ] ]
K = 2
# Function Call
maxSumSubmatrix(matrix, K)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum possible
// sum of arectangle which is less than K
static int maxSubarraySum(int[] sum,int k, int row)
{
int curSum = 0, curMax = Int32.MinValue;
// Stores the values (cum_sum - K)
HashSet<int> sumSet = new HashSet<int>();
// Insert 0 into the set sumSet
sumSet.Add(0);
// Traverse over the rows
for(int r = 0; r < row; ++r)
{
// Get cumulative sum from [0 to i]
curSum += sum[r];
// Search for upperbound of
// (cSum - K) in the hashmap
List<int> list = new List<int>();
list.AddRange(sumSet);
int it = list.LastIndexOf(curSum - k);
// If upper_bound of (cSum - K)
// exists, then update max sum
if (it > -1)
{
curMax = Math.Max(curMax,
curSum - it);
}
// Insert cumulative value
// in the hashmap
sumSet.Add(curSum);
}
// Return the maximum sum
// which is less than K
return curMax;
}
// Function to find the maximum sum of
// rectangle such that its sum is no
// larger than K
static void maxSumSubmatrix(int[,] matrix, int k)
{
// Stores the number of rows
// and columns
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);
// Store the required result
int ret = Int32.MinValue;
// Set the left column
for(int i = 0; i < col; ++i)
{
int[] sum = new int[row];
// Set the right column for the
// left column set by outer loop
for(int j = i; j < col; ++j)
{
// Calculate sum between the
// current left and right
// for every row
for(int r = 0; r < row; ++r)
{
sum[r] += matrix[r, j];
}
// Stores the sum of rectangle
int curMax = maxSubarraySum(
sum, k, row);
// Update the overall maximum sum
ret = Math.Max(ret, curMax);
}
}
// Print the result
Console.Write(ret);
}
// Driver Code
static public void Main()
{
int[,] matrix = { { 1, 0, 1 },
{ 0, -2, 3 } };
int K = 2;
// Function Call
maxSumSubmatrix(matrix, K);
}
}
// This code is contributed by rag2127
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum possible
// sum of arectangle which is less than K
function maxSubarraySum(sum,k,row)
{
let curSum = 0, curMax = Number.MIN_VALUE;
// Stores the values (cum_sum - K)
let sumSet = new Set();
// Insert 0 into the set sumSet
sumSet.add(0);
// Traverse over the rows
for(let r = 0; r < row; ++r)
{
// Get cumulative sum from [0 to i]
curSum += sum[r];
// Search for upperbound of
// (cSum - K) in the hashmap
let list = [];
list=Array.from(sumSet);
let it = list.lastIndexOf(curSum - k);
// If upper_bound of (cSum - K)
// exists, then update max sum
if (it >-1)
{
curMax = Math.max(curMax,
curSum - it);
}
// Insert cumulative value
// in the hashmap
sumSet.add(curSum);
}
// Return the maximum sum
// which is less than K
return curMax;
}
// Function to find the maximum sum of
// rectangle such that its sum is no
// larger than K
function maxSumSubmatrix(matrix, k)
{
// Stores the number of rows
// and columns
let row = matrix.length;
let col = matrix[0].length;
// Store the required result
let ret = Number.MIN_VALUE;
// Set the left column
for(let i = 0; i < col; ++i)
{
let sum = new Array(row);
for(let j=0;j<row;j++)
sum[j]=0;
// Set the right column for the
// left column set by outer loop
for(let j = i; j < col; ++j)
{
// Calculate sum between the
// current left and right
// for every row
for(let r = 0; r < row; ++r)
{
sum[r] += matrix[r][j];
}
// Stores the sum of rectangle
let curMax = maxSubarraySum(
sum, k, row);
// Update the overall maximum sum
ret = Math.max(ret, curMax);
}
}
// Print the result
document.write(ret);
}
// Driver Code
let matrix=[[ 1, 0, 1 ],
[ 0, -2, 3 ]];
let K = 2;
maxSumSubmatrix(matrix, K)
// This code is contributed by patel2127
</script>
Producción:
2
Complejidad de tiempo: O(N 3 *log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rutvikchandla3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA