Dada una array nxn de enteros. El problema es encontrar la subarray rectangular de área más grande que tenga una suma divisible por el valor k dado .
Ejemplos:
Input : mat[][] = { {1, 2, -1, -4},
{-8, -3, 4, 2},
{3, 8, 10, 1},
{-4, -1, 1, 7} }
k = 5
Output : Area = 12
(Top, Left): (0, 0)
(Bottom, Right): (2, 3)
The sub-matrix is:
| 1, 2, -1, -4 |
| -8, -3, 4, 2 |
| 3, 8, 10, 1 |
Enfoque ingenuo: verifique cada rectángulo posible en una array 2D dada que tenga una suma divisible por ‘k’ e imprima el más grande. Esta solución requiere 4 bucles anidados y la complejidad de tiempo de esta solución sería O(n^4).
Enfoque eficiente: el subarreglo más largo que tiene una suma divisible por k para un arreglo 1-D puede usarse para reducir la complejidad del tiempo a O(n^3). La idea es arreglar las columnas izquierda y derecha una por una y encontrar el subarreglo más largo que tenga una suma divisible por ‘k’ para filas contiguas para cada par de columnas izquierda y derecha. Básicamente, encontramos números de fila superior e inferior (que son parte de la subarray más grande) 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.
Ahora, aplique el subarreglo más largo que tenga una suma divisible por k 1D en temp[], y obtenga el subarreglo más largo que tenga una suma divisible por ‘k’ de temp[]. Esta longitud sería la longitud máxima posible con la izquierda y la derecha como columnas límite. Establezca los índices de fila ‘superior’ e ‘inferior’ para el par de columnas izquierda derecha y calcule el área. De manera similar, obtenga los índices superior, inferior, izquierdo y derecho para otras subarrays que tengan una suma divisible por ‘k’ e imprima el que tenga el área máxima.
Implementación:
C++
// C++ implementation to find largest rectangular
// sub-matrix having sum divisible by k
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
// function to find the longest subarray with sum divisible
// by k. The function stores starting and ending indexes of
// the subarray at addresses pointed by start and finish
// pointers respectively.
void longSubarrWthSumDivByK(int arr[], int n, int k,
int& start, int& finish)
{
// unordered map 'um' implemented as
// hash table
unordered_map<int, int> um;
// 'mod_arr[i]' stores (sum[0..i] % k)
int mod_arr[n];
int curr_sum = 0, max = 0;
// traverse arr[] and build up the
// array 'mod_arr[]'
for (int i = 0; i < n; i++) {
curr_sum += arr[i];
// as the sum can be negative, taking modulo twice
mod_arr[i] = ((curr_sum % k) + k) % k;
}
for (int i = 0; i < n; i++) {
// if true then sum(0..i) is divisible
// by k
if (mod_arr[i] == 0) {
// update variables
max = i + 1;
start = 0;
finish = i;
}
// if value 'mod_arr[i]' not present in 'um'
// then store it in 'um' with index of its
// first occurrence
else if (um.find(mod_arr[i]) == um.end())
um[mod_arr[i]] = i;
else
// if true, then update variables
if (max < (i - um[mod_arr[i]])) {
max = i - um[mod_arr[i]];
start = um[mod_arr[i]] + 1;
finish = i;
}
}
}
// function to find largest rectangular sub-matrix
// having sum divisible by k
void findLargestSubmatrix(int mat[SIZE][SIZE], int n, int k)
{
// Variables to store the final output
int finalLeft, finalRight, finalTop, finalBottom;
int left, right, i, maxArea = 0;
int temp[n], start, finish;
// Set the left column
for (left = 0; left < n; 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 < n; right++) {
// Calculate sum between current left and
// right for every row 'i'
for (i = 0; i < n; ++i)
temp[i] += mat[i][right];
// The longSubarrWthSumDivByK() function sets
// the values of 'start' and 'finish'. So
// submatrix having sum divisible by 'k' between
// (start, left) and (finish, right) which is
// the largest submatrix with boundary columns
// strictly as left and right.
longSubarrWthSumDivByK(temp, n, k, start, finish);
// Calculate current area and compare it with
// maximum area so far. If maxArea is less, then
// update maxArea and other output values
if (maxArea < ((right - left + 1) *
(finish - start + 1))) {
finalLeft = left;
finalRight = right;
finalTop = start;
finalBottom = finish;
maxArea = (right - left + 1) * (finish - start + 1);
}
}
}
// Print final values
cout << "(Top, Left): (" << finalTop << ", "
<< finalLeft << ")\n";
cout << "(Bottom, Right): (" << finalBottom << ", "
<< finalRight << ")\n";
cout << "Area: " << maxArea;
}
// Driver program to test above functions
int main()
{
int mat[SIZE][SIZE] = { { 1, 2, -1, -4 },
{ -8, -3, 4, 2 },
{ 3, 8, 10, 1 },
{ -4, -1, 1, 7 } };
int n = 4, k = 5;
findLargestSubmatrix(mat, n, k);
return 0;
}
Java
// Java implementation to find largest
// rectangular sub-matrix having sum
// divisible by k
import java.util.*;
class GFG{
static final int SIZE = 10;
static int start, finish;
// Function to find the longest subarray
// with sum divisible by k. The function
// stores starting and ending indexes of
// the subarray at addresses pointed by
// start and finish pointers respectively
static void longSubarrWthSumDivByK(int arr[],
int n, int k)
{
// unordered map 'um' implemented as
// hash table
HashMap<Integer, Integer> um = new HashMap<>();
// 'mod_arr[i]' stores (sum[0..i] % k)
int []mod_arr = new int[n];
int curr_sum = 0, max = 0;
// Traverse arr[] and build up the
// array 'mod_arr[]'
for(int i = 0; i < n; i++)
{
curr_sum += arr[i];
// As the sum can be negative,
// taking modulo twice
mod_arr[i] = ((curr_sum % k) + k) % k;
}
for(int i = 0; i < n; i++)
{
// If true then sum(0..i) is
// divisible by k
if (mod_arr[i] == 0)
{
// Update variables
max = i + 1;
start = 0;
finish = i;
}
// If value 'mod_arr[i]' not present
// in 'um' then store it in 'um' with
// index of its first occurrence
else if (!um.containsKey(mod_arr[i]))
um.put(mod_arr[i], i);
else
// If true, then update variables
if (max < (i - um.get(mod_arr[i])))
{
max = i - um.get(mod_arr[i]);
start = um.get(mod_arr[i]) + 1;
finish = i;
}
}
}
// Function to find largest rectangular
// sub-matrix having sum divisible by k
static void findLargestSubmatrix(int mat[][],
int n, int k)
{
// Variables to store the final output
int finalLeft = 0, finalRight = 0,
finalTop = 0, finalBottom = 0;
int left, right, i, maxArea = 0;
int []temp = new int[n];
// Set the left column
for(left = 0; left < n; left++)
{
// Initialize all elements of temp as 0
Arrays.fill(temp, 0);
// Set the right column for the left
// column set by outer loop
for(right = left; right < n; right++)
{
// Calculate sum between current
// left and right for every row 'i'
for(i = 0; i < n; ++i)
temp[i] += mat[i][right];
// The longSubarrWthSumDivByK() function
// sets the values of 'start' and 'finish'.
// So submatrix having sum divisible by 'k'
// between (start, left) and (finish, right)
// which is the largest submatrix with
// boundary columns strictly as left and right.
longSubarrWthSumDivByK(temp, n, k);
// Calculate current area and compare it
// with maximum area so far. If maxArea
// is less, then update maxArea and other
// output values
if (maxArea < ((right - left + 1) *
(finish - start + 1)))
{
finalLeft = left;
finalRight = right;
finalTop = start;
finalBottom = finish;
maxArea = (right - left + 1) *
(finish - start + 1);
}
}
}
// Print final values
System.out.print("(Top, Left): (" +
finalTop + ", " +
finalLeft + ")\n");
System.out.print("(Bottom, Right): (" +
finalBottom + ", " +
finalRight + ")\n");
System.out.print("Area: " + maxArea);
}
// Driver code
public static void main(String[] args)
{
int [][]mat = { { 1, 2, -1, -4 },
{ -8, -3, 4, 2 },
{ 3, 8, 10, 1 },
{ -4, -1, 1, 7 } };
int n = 4, k = 5;
findLargestSubmatrix(mat, n, k);
}
}
// This code is contributed by Amit Katiyar
C#
// C# implementation to find largest
// rectangular sub-matrix having sum
// divisible by k
using System;
using System.Collections.Generic;
class GFG{
//static readonly int SIZE = 10;
static int start, finish;
// Function to find the longest subarray
// with sum divisible by k. The function
// stores starting and ending indexes of
// the subarray at addresses pointed by
// start and finish pointers respectively
static void longSubarrWthSumDivByK(int []arr,
int n, int k)
{
// unordered map 'um' implemented as
// hash table
Dictionary<int,
int> um = new Dictionary<int,
int>();
// 'mod_arr[i]' stores (sum[0..i] % k)
int []mod_arr = new int[n];
int curr_sum = 0, max = 0;
// Traverse []arr and build up the
// array 'mod_arr[]'
for(int i = 0; i < n; i++)
{
curr_sum += arr[i];
// As the sum can be negative,
// taking modulo twice
mod_arr[i] = ((curr_sum % k) + k) % k;
}
for(int i = 0; i < n; i++)
{
// If true then sum(0..i) is
// divisible by k
if (mod_arr[i] == 0)
{
// Update variables
max = i + 1;
start = 0;
finish = i;
}
// If value 'mod_arr[i]' not present
// in 'um' then store it in 'um' with
// index of its first occurrence
else if (!um.ContainsKey(mod_arr[i]))
um.Add(mod_arr[i], i);
else
// If true, then update variables
if (max < (i - um[mod_arr[i]]))
{
max = i - um[mod_arr[i]];
start = um[mod_arr[i]] + 1;
finish = i;
}
}
}
// Function to find largest rectangular
// sub-matrix having sum divisible by k
static void findLargestSubmatrix(int [,]mat,
int n, int k)
{
// Variables to store the readonly output
int finalLeft = 0, finalRight = 0,
finalTop = 0, finalBottom = 0;
int left, right, i, maxArea = 0;
int []temp;
// Set the left column
for(left = 0; left < n; left++)
{
// Initialize all elements of temp as 0
temp = new int[n];
// Set the right column for the left
// column set by outer loop
for(right = left; right < n; right++)
{
// Calculate sum between current
// left and right for every row 'i'
for(i = 0; i < n; ++i)
temp[i] += mat[i,right];
// The longSubarrWthSumDivByK() function
// sets the values of 'start' and 'finish'.
// So submatrix having sum divisible by 'k'
// between (start, left) and (finish, right)
// which is the largest submatrix with
// boundary columns strictly as left and right.
longSubarrWthSumDivByK(temp, n, k);
// Calculate current area and compare it
// with maximum area so far. If maxArea
// is less, then update maxArea and other
// output values
if (maxArea < ((right - left + 1) *
(finish - start + 1)))
{
finalLeft = left;
finalRight = right;
finalTop = start;
finalBottom = finish;
maxArea = (right - left + 1) *
(finish - start + 1);
}
}
}
// Print readonly values
Console.Write("(Top, Left): (" +
finalTop + ", " +
finalLeft + ")\n");
Console.Write("(Bottom, Right): (" +
finalBottom + ", " +
finalRight + ")\n");
Console.Write("Area: " + maxArea);
}
// Driver code
public static void Main(String[] args)
{
int [,]mat = { { 1, 2, -1, -4 },
{ -8, -3, 4, 2 },
{ 3, 8, 10, 1 },
{ -4, -1, 1, 7 } };
int n = 4, k = 5;
findLargestSubmatrix(mat, n, k);
}
}
// This code is contributed by Princi Singh
Python3
# Python implementation to find largest rectangular
# sub-matrix having sum divisible by k
start = 0
finish = 0
# function to find the longest subarray with sum divisible
# by k. The function stores starting and ending indexes of
# the subarray at addresses pointed by start and finish
# pointers respectively.
def longSubarrWthSumDivByK(arr, n, k):
# unordered map 'um' implemented as
# hash table
global start,finish
um = {}
# 'mod_arr[i]' stores (sum[0..i] % k)
mod_arr = [0 for i in range(n)]
curr_sum,Max = 0,0
# traverse arr[] and build up the
# array 'mod_arr[]'
for i in range(n):
curr_sum += arr[i]
# as the sum can be negative, taking modulo twice
mod_arr[i] = ((curr_sum % k) + k) % k
for i in range(n):
# if true then sum(0..i) is divisible
# by k
if (mod_arr[i] == 0):
# update variables
max = i + 1
start = 0
finish = i
# if value 'mod_arr[i]' not present in 'um'
# then store it in 'um' with index of its
# first occurrence
elif (mod_arr[i] not in um):
um[mod_arr[i]] = i
else:
# if true, then update variables
if (Max < (i - um[mod_arr[i]])):
Max = i - um[mod_arr[i]]
start = um[mod_arr[i]] + 1
finish = i
# function to find largest rectangular sub-matrix
# having sum divisible by k
def findLargestSubmatrix(mat, n, k):
# Variables to store the final output
finalLeft, finalRight, finalTop, finalBottom = 0,0,0,0
left, right, i, maxArea = 0,0,0,0
temp = [0 for i in range(n)]
# Set the left column
for left in range(n):
# Set the right column for the left column
# set by outer loop
for right in range(left,n):
# Calculate sum between current left and
# right for every row 'i'
for i in range(n):
temp[i] += mat[i][right]
# The longSubarrWthSumDivByK() function sets
# the values of 'start' and 'finish'. So
# submatrix having sum divisible by 'k' between
# (start, left) and (finish, right) which is
# the largest submatrix with boundary columns
# strictly as left and right.
longSubarrWthSumDivByK(temp, n, k)
# Calculate current area and compare it with
# maximum area so far. If maxArea is less, then
# update maxArea and other output values
if (maxArea < ((right - left + 1) * (finish - start + 1))):
finalLeft = left
finalRight = right
finalTop = start
finalBottom = finish
maxArea = (right - left + 1) * (finish - start + 1)
# Print final values
print(f"(Top, Left): ({finalTop}, {finalLeft})")
print(f"(Bottom, Right): ({finalBottom}, {finalRight})")
print(f"Area: {maxArea}")
# Driver program to test above functions
mat = [ [ 1, 2, -1, -4 ],
[ -8, -3, 4, 2 ],
[ 3, 8, 10, 1 ],
[ -4, -1, 1, 7 ] ]
n,k = 4,5
findLargestSubmatrix(mat, n, k)
# code is contributed by shinjanpatra
Producción
(Top, Left): (0, 0) (Bottom, Right): (2, 3) Area: 12
Complejidad de tiempo: O(n^3).
Espacio Auxiliar: O(n).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA