Find the maximum area of the matrix with the sum of elements less than or equal to k

Question

Could you advise the algorithm that solves the following problem?

Given a rectangular matrix of size nxm and the number k. We need to find a submatrix (the original matrix is also considered a submatrix) of the largest area (the number of columns multiplied by the number of rows), whose sum of elements is less than or equal to k. Return the area of this matrix. All elements of the matrix and the number k are positive integers. The algorithm must have complexity below O (n ^ 6). You can use additional structures based on the matrix.

At the moment, I realized that the matrix of sums of columns and rows can help: a matrix of sums of tables for a matrix with elements of the form

$a_{i,j},i=0..n,0..m$

row total matrix:

$r_{i,j}=\sum_{k=0}^{j} a_{i,k}$

column sums matrix:

$c_{i,j}=\sum_{k=0}^{i} a_{k,j}$

That is, for the matrix of the form

$\begin{pmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9\\ \end{pmatrix}$

row total matrix:

$\begin{pmatrix} 1 & 3 & 6\\ 4 & 9 & 15\\ 7 & 15 & 24\\ \end{pmatrix}$

column sums matrix:

$\begin{pmatrix} 1 & 2 & 3\\ 5 & 7 & 9\\ 12 & 15 & 18\\ \end{pmatrix}$

Another read that you can use the sum matrix of submatrices of the form

$S_{i,j}=\sum_{r=0}^{i}\sum_{s=0}^{j}a_{r,s}$

which for the reduced matrix looks like this

$\begin{pmatrix} 1 & 3 & 6\\ 5 & 12 & 21\\ 12 & 27 & 45 \end{pmatrix}$

This matrix can be used to find the sum of the submatrix, for example, to find the value of an element

$a_{2,2}$

matrices

$\begin{pmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9\\ \end{pmatrix}$

as $S_{2,2}-S_{1,2}-S_{2,1}+S_{1,1}=45-27-21+12=9$

If M x N, then the direct search is obtained as O (n ^ 3), if n is N, then the direct search is obtained only as your O (n ^ 6), only it is more logical to set n as M x N, therefore it is not clear a little bit ...
by n I mean one of the dimensions of the matrix, the naive algorithm has complexity O (n ^ 6)
@MarcoSobolev, if this is nevertheless exactly one of the sizes, then the second one can only be fixed.
Optimization comes to my mind only too complicated, so that I can immediately write some code.
If the enumeration of all subsets can be implemented while preserving the complexity O (n ^ 2) so that the subsets of the same size P x Q are sequentially iterated, then the sum can be considered as a fast two-dimensional moving average method.
Its complexity is still O (n), but at least the one-dimensional version lends itself to some optimization .
Assuming that the number of elements in the matrix is O(n**2) .
The most naive approach enumerates all possible child matrices (i, j, nrows, ncolumns) - O(n**4) and naively calculates the sum from the very beginning n * m - O(n**2) -> O(n**6) algorithm.
If you use the S [i, j] matrix, then you can calculate the sum for O (1): Sum(i,j,nrows,ncolumns) = S[i+nrows,j+ncolumns] - S[i+nrows,j] - S[i,j+ncolumns] +S[i,j] that is, using S [i, j], the naive algorithm becomes O(n**4) in time and O(n**2) in memory.

Find the maximum area of ​​the matrix with the sum of elements less than or equal to k

0

More articles:

Find the maximum area of the matrix with the sum of elements less than or equal to k