Максимальный размер квадрата, при котором сумма всех подматриц такого размера меньше K
Опубликовано: 7 Января, 2022
Учитывая матрицу целых чисел N x M и целое число K , задача состоит в том, чтобы найти размер максимальной квадратной подматрицы (S x S) , такой, чтобы все квадратные подматрицы данной матрицы этого размера имели сумму меньше K.
Примеры:
Ввод: K = 30
мат [N] [M] = {{1, 2, 3, 4, 6},
{5, 3, 8, 1, 2},
{4, 6, 7, 5, 5},
{2, 4, 8, 9, 4}};
Выход: 2
Объяснение:
Все субматрицы размером 2 x 2
иметь сумму менее 30
Ввод: K = 100
мат [N] [M] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
Выход: 3
Объяснение:
Все субматрицы размером 3 x 3
иметь сумму менее 100Наивный подход Основное решение - выбрать размер S подматрицы, найти все подматрицы этого размера и проверить, что сумма всех подматриц меньше заданной суммы, тогда как это можно улучшить, вычислив сумму матрица с использованием этого подхода. Следовательно, задача состоит в том, чтобы выбрать максимально возможный размер, а также начальную и конечную позиции всех возможных подматриц. Благодаря чему общая временная сложность составит O (N 3 ).
Below is the implementation of the above approach:
C++
// C++ implementation to find the// maximum size square submatrix// such that their sum is less than K#include <bits/stdc++.h>using namespace std;// Size of matrix#define N 4#define M 5// Function to preprocess the matrix// for computing the sum of every// possible matrix of the given sizevoid preProcess(int mat[N][M], int aux[N][M]){ // Loop to copy the first row // of the matrix into the aux matrix for (int i = 0; i < M; i++) aux[0][i] = mat[0][i]; // Computing the sum column-wise for (int i = 1; i < N; i++) for (int j = 0; j < M; j++) aux[i][j] = mat[i][j] + aux[i - 1][j]; // Computing row wise sum for (int i = 0; i < N; i++) for (int j = 1; j < M; j++) aux[i][j] += aux[i][j - 1];}// Function to find the sum of a// submatrix with the given indicesint sumQuery(int aux[N][M], int tli, int tlj, int rbi, int rbj){ // Overall sum from the top to // right corner of matrix int res = aux[rbi][rbj]; // Removing the sum from the top // corer of the matrix if (tli > 0) res = res - aux[tli - 1][rbj]; // Remove the overlapping sum if (tlj > 0) res = res - aux[rbi][tlj - 1]; // Add the sum of top corner // which is substracted twice if (tli > 0 && tlj > 0) res = res + aux[tli - 1][tlj - 1]; return res;}// Function to find the maximum// square size possible with the// such that every submatrix have// sum less than the given sumint maximumSquareSize(int mat[N][M], int K){ int aux[N][M]; preProcess(mat, aux); // Loop to choose the size of matrix for (int i = min(N, M); i >= 1; i--) { bool satisfies = true; // Loop to find the sum of the // matrix of every possible submatrix for (int x = 0; x < N; x++) { for (int y = 0; y < M; y++) { if (x + i - 1 <= N - 1 && y + i - 1 <= M - 1) { if (sumQuery(aux, x, y, x + i - 1, y + i - 1) > K) satisfies = false; } } } if (satisfies == true) return (i); } return 0;}// Driver Codeint main(){ int K = 30; int mat[N][M] = { { 1, 2, 3, 4, 6 }, { 5, 3, 8, 1, 2 }, { 4, 6, 7, 5, 5 }, { 2, 4, 8, 9, 4 } }; cout << maximumSquareSize(mat, K); return 0;} |
Java
// Java implementation to find the// maximum size square submatrix// such that their sum is less than Kclass GFG{ // Size of matrixstatic final int N = 4;static final int M = 5; // Function to preprocess the matrix// for computing the sum of every// possible matrix of the given sizestatic void preProcess(int [][]mat, int [][]aux){ // Loop to copy the first row // of the matrix into the aux matrix for (int i = 0; i < M; i++) aux[0][i] = mat[0][i]; // Computing the sum column-wise for (int i = 1; i < N; i++) for (int j = 0; j < M; j++) aux[i][j] = mat[i][j] + aux[i - 1][j]; // Computing row wise sum for (int i = 0; i < N; i++) for (int j = 1; j < M; j++) aux[i][j] += aux[i][j - 1];} // Function to find the sum of a// submatrix with the given indicesstatic int sumQuery(int [][]aux, int tli, int tlj, int rbi, int rbj){ // Overall sum from the top to // right corner of matrix int res = aux[rbi][rbj]; // Removing the sum from the top // corer of the matrix if (tli > 0) res = res - aux[tli - 1][rbj]; // Remove the overlapping sum if (tlj > 0) res = res - aux[rbi][tlj - 1]; // Add the sum of top corner // which is substracted twice if (tli > 0 && tlj > 0) res = res + aux[tli - 1][tlj - 1]; return res;} // Function to find the maximum// square size possible with the// such that every submatrix have// sum less than the given sumstatic int maximumSquareSize(int [][]mat, int K){ int [][]aux = new int[N][M]; preProcess(mat, aux); // Loop to choose the size of matrix for (int i = Math.min(N, M); i >= 1; i--) { boolean satisfies = true; // Loop to find the sum of the // matrix of every possible submatrix for (int x = 0; x < N; x++) { for (int y = 0; y < M; y++) { if (x + i - 1 <= N - 1 && y + i - 1 <= M - 1) { if (sumQuery(aux, x, y, x + i - 1, y + i - 1) > K) satisfies = false; } } } if (satisfies == true) return (i); } return 0;} // Driver Codepublic static void main(String[] args){ int K = 30; int mat[][] = { { 1, 2, 3, 4, 6 }, { 5, 3, 8, 1, 2 }, { 4, 6, 7, 5, 5 }, { 2, 4, 8, 9, 4 } }; System.out.print(maximumSquareSize(mat, K));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation to find the# maximum size square submatrix# such that their sum is less than K# Size of matrixN = 4M = 5# Function to preprocess the matrix# for computing the sum of every# possible matrix of the given sizedef preProcess(mat, aux): # Loop to copy the first row # of the matrix into the aux matrix for i in range (M): aux[0][i] = mat[0][i] # Computing the sum column-wise for i in range (1, N): for j in range (M): aux[i][j] = (mat[i][j] + aux[i - 1][j]) # Computing row wise sum for i in range (N): for j in range (1, M): aux[i][j] += aux[i][j - 1]# Function to find the sum of a# submatrix with the given indicesdef sumQuery(aux, tli, tlj, rbi, rbj): # Overall sum from the top to # right corner of matrix res = aux[rbi][rbj] # Removing the sum from the top # corer of the matrix if (tli > 0): res = res - aux[tli - 1][rbj] # Remove the overlapping sum if (tlj > 0): res = res - aux[rbi][tlj - 1] # Add the sum of top corner # which is substracted twice if (tli > 0 and tlj > 0): res = (res + aux[tli - 1][tlj - 1]) return res# Function to find the maximum# square size possible with the# such that every submatrix have# sum less than the given sumdef maximumSquareSize(mat, K): aux = [[0 for x in range (M)] for y in range (N)] preProcess(mat, aux) # Loop to choose the size of matrix for i in range (min(N, M), 0, -1): satisfies = True # Loop to find the sum of the # matrix of every possible submatrix for x in range (N): for y in range (M) : if (x + i - 1 <= N - 1 and y + i - 1 <= M - 1): if (sumQuery(aux, x, y, x + i - 1, y + i - 1) > K): satisfies = False if (satisfies == True): return (i) return 0# Driver Codeif __name__ == "__main__": K = 30 mat = [[1, 2, 3, 4, 6], [5, 3, 8, 1, 2], [4, 6, 7, 5, 5], [2, 4, 8, 9, 4]] print( maximumSquareSize(mat, K))# This code is contributed by Chitranayal |
C#
// C# implementation to find the// maximum size square submatrix// such that their sum is less than Kusing System;public class GFG{ // Size of matrixstatic readonly int N = 4;static readonly int M = 5; // Function to preprocess the matrix// for computing the sum of every// possible matrix of the given sizestatic void preProcess(int [,]mat, int [,]aux){ // Loop to copy the first row // of the matrix into the aux matrix for (int i = 0; i < M; i++) aux[0,i] = mat[0,i]; // Computing the sum column-wise for (int i = 1; i < N; i++) for (int j = 0; j < M; j++) aux[i,j] = mat[i,j] + aux[i - 1,j]; // Computing row wise sum for (int i = 0; i < N; i++) for (int j = 1; j < M; j++) aux[i,j] += aux[i,j - 1];} // Function to find the sum of a// submatrix with the given indicesstatic int sumQuery(int [,]aux, int tli, int tlj, int rbi, int rbj){РЕКОМЕНДУЕМЫЕ СТАТЬИ |