title: Maximum subarray of size HxW within a big 2D bit matrix
body: <p>I have a big NxN bit array with K ones (everything else is zero). Coordinates of all non-zero points are known - in other words this NxN array can be represented as an array of K pairs each containing x and y coords of a non-zero point.</p>
  <p>Given a submatrix of HxW size, I need place it on my original NxN array such that it covers the most non-zero points.</p>
  <p><strong>Input:</strong> Height <strong>H</strong> and width <strong>W</strong> of submatrix</p>
  <p><strong>Output:</strong> <strong>x</strong> and <strong>y</strong> coords of HxW subarray which has the most ones within itself</p>
  <p>Similar question was answered before: <a href="https://stackoverflow.com/questions/39937212/maximum-subarray-of-size-hxw-within-a-2d-matrix">Maximum subarray of size HxW within a 2D matrix</a> but in my problem is a bit more complicated since N is huge, in my case:
  N=60000, K&lt;15000, H,W&lt;10000.</p>
  <p>Creating 60000x60000 array would be a memory kill, even if it's an array of bits. That's why I came up with idea of representing that array with all non zero points: one dimensional array of K pairs.</p>
  <p>Everything I can come up with is super both memory and time unefficient, I'm looking for any solution that won't eat all my ram.
  Here's how it's meant to look like: the output would be point (4,3) since HxW subarray, which starts at this point, contains the most ones.</p>
  <p><a href="https://i.stack.imgur.com/13MlJ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/13MlJ.png" alt="enter image description here" /></a></p>