title: Finding the maximum area in given binary data
body: <p>I have a problem with describing algorithm for finding maximum rectangular area of binary data, where 1 occurs k-times more often than 0. Data is always n^2 bits like this:</p>
  
  <p>For example data for n = 4 looks like:<br><br>
     1 0 1 0<br>
     0 0 1 1<br>
     0 1 1 1<br>
     1 1 0 1<br></p>
  
  <p>Value of k can be 1 .. j (k = 1 means, that number of 0 and 1 is equal).<br><br>
  For above example of data and for k = 1 solution is:</p>
  
  <p><strong>1 0 1 0</strong>   &lt;- 4 x '0' and 4 x '1'<br>
     <strong>0 0 1 1</strong><br>
     0 1 1 1<br>
     1 1 0 1<br></p>
  
  <p>But in this example:<br>
  1 1 1 0<br>
  0 1 0 0<br>
  0 0 0 0<br>
  0 1 1 1<br></p>
  
  <p>Solution would be:<br>
  1 <strong>1 1 0</strong><br>
  0 <strong>1 0 0</strong><br>
  0 <strong>0 0 0</strong><br>
  0 <strong>1 1 1</strong><br></p>
  
  <p>I tried with few brute force algorithms but for n > 20 it is getting too slow. Can you advise me how I should solve this problem?</p>
  
  <hr>
  
  <p>As RBerteig proposed - the problem can be also described like that: "In a given square bitmap with cells set to 1 or 0 by some arbitrary process, find the largest rectangular area where the 1's and 0's occur in a specified ratio, k."</p>