Example: Max Size Rectangle of all 1 in matrix

You are given a 0/1 matrix. Find the maximums rectangle size.

• X:

--	0	1	2	3	4	5
0	1	0	0	1	1	1
1	1	0	1	1	0	1
2	0	1	1	1	1	1
3	0	0	1	1	1	1

• Analyze row by row using a support vector
  • if x[i,j] == 1 => s[j] = s[j] + 1 else s[j] == 0
  • For example:
    • | 1 | 0 | 0 | 1 | 1 | 1 | first row
    • | 2 | 0 | 1 | 2 | 0 | 2 | second row
    • | 0 | 1 | 2 | 3 | 1 | 3 | thirdrow
• You can then use the max histogram area approach to get the current max area and update the maxArea if bigger

// x[0..n, 0..m]
maxSubRect(x)
    let d[0..m] be an array initialized to 0
    maxA = 0
    for i = 0 to n
        for j = 0 to m
            if x[i,j] == 1
                d[j] = d[j] + 1
            else 
                d[j] = 0
        tmp = maxHistogramArea(d)
        if tmp > maxA
            maxA = tmp
    return maxA