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
Post a Comment