Given a 2d array N*M made of only 1's and 0's . I need to find a maximum subarray(square or rectangle) between two rows of the given 2d array which has all ones inside it. I need to find count of ones in this maximum subarray
EXAMPLE : Let N=4 and M=5 and the array be
1 0 1 1 0
1 0 1 1 1
0 1 1 1 1
0 0 0 0 1
Now if their are Q(say here it be 2) queries each describing upper and lower row between which we need to find this subarray.
Query 1 : 1 1(means start at row 1 and end also at row 1).Then we can clearly see answer will be 2
Query 2 : 2 3(means start at row 2 and end at row 3).Then answer will be 6 here.
Now,if queries can be very large in number(say upto 10^6) .How to tackle this problem