algorithm - Submatrix of given size with largest sum -


i have n*n grid filled zeros. update n random points on , set value number greater equal 1. also, given value of "l".

we want find sub-matrix of size l*l in grid such the sum of elements in sub-matrix maximum. if there multiple answers, possible output coordinates of such sub-matrix.

constraints: 1 <= n <= 50000, 1 <= l <= 50000.

i know how solve problem in o(n2) considering sub-matrices of sizes l*l, using prefix sums calculate sum. problem here cannot declare such large matrix due constraints on n.

is there efficient way tackle problem? grateful.


Comments