CareerCup

What 's wrong with you people? Stop posting these sheets of code. Write your idea first. Nobody wants to waste time reading tons of your code.

Go through the matrix row by row; for each row, record the maximum height each column can reach. Then it becomes a skyline problem, which can be solved in O(n).
Overall, the time complexity is O(n * n) and the space complexity is O(n);

#include <vector>
#include <stack>

using namespace std;

int get_max_area(const vector<vector<int> >& m) {
    int result = 0;
    vector<int> h(m[0].size() + 1, 0);
    for (int i = 0; i < m.size(); ++i) {
        stack<int> s;
        for (int j = 0; j <= m[i].size(); ++j) {
            if (j < m[i].size())
                h[j] = (m[i][j] == 0) ? 0 : h[j] + 1;
            while (!s.empty() && h[s.top()] > h[j]) {
                int top = s.top();
                s.pop();
                int begin = s.empty() ? 0 : s.top() + 1;
                result = max(result, h[top] * (j - begin));
            }
            s.push(j);
        }
    }
    return result;
}

public class RectangleArea
{
public static void main(String[] args)
{
int [][] area = {{0,0,0,0,1,0,0},
{0,0,0,0,1,0,0},
{0,0,1,1,1,1,1},
{0,0,0,0,1,0,0},
{0,0,0,0,0,0,0}};

int maxarea = 0;
int startx =0;
int starty = 0;
int xlength = 0;
int ylength = 0;

for(int j=0;j<area.length;j++) //j -> y axis
{
for(int i=0;i<area[j].length;i++)//i -> x axis
{
int x = 0;//x de o turda ne kadar uzayabilir
int y = 0;//y de o turda ne kadar uzayabilir.

if(area[j][i] == 1)
{
int ii = 1;
int jj = 1;
int tempmaxarea = 1;
while(i+ii < area[j].length && area[j][i+ii] == 1)//detect x expansion
{
x++;
ii++;
}
while(j+jj < area.length && area[j+jj][i] == 1)//detect y expansion
{
y++;
jj++;
}
int breakxloopindex = x+1;// asagidaki aciklamanin x icin olani..defaultta max cerceve boyutunda tut.. 0 a rastladikca kucultursun
for(int l=0;l<=y;l++)
{
for(int k=0;k<=x;k++)
{
if(area[j+l][i+k] ==0)
{
if(breakxloopindex > k)
{
breakxloopindex = k;
}
}
}
tempmaxarea = (breakxloopindex)*(1+l);
if(maxarea < tempmaxarea)
{
maxarea = tempmaxarea;
startx = i;
starty = j;
xlength = breakxloopindex;
ylength = l+1;
}
}
}
}
}

System.out.println("Max area is:" + maxarea);
System.out.println("startx: "+ startx + " starty: "+starty);
System.out.println("xlength:"+ xlength + " ylength:"+ylength);
}
}

As Sam nicely suggested, previous code was wrong so I replaced it with this one. This one runs in O(WH) = O(N^2) for N = max(W, H).

The idea is we find something like cumulative sum over all columns. So when at row "i", w[j] is the sum of all the previous consecutive "1"s.

From "w" we can find the rectangles up to current row in O(N) time. For example, if w = [1 1 2 2 2 1], the largest rectangle has an area of 6.

Here is the python code:

m = open('sample.txt', 'r').read().rstrip().split('\n')

def getMaxRectOnRow(w):
    stack = []
    pos, max_area, rect = 0, 0, 0
    while pos < len(w):
        next_value = w[pos]
        if len(stack) == 0:
            stack.append([next_value, 1])
        else:
            stacktop = stack.pop(len(stack) - 1)
            if stacktop[0] < next_value:
                stack.append(stacktop)
                stack.append([next_value, 1])
            elif stacktop[0] == next_value:
                stacktop[1] += 1
                stack.append(stacktop)
            else:
                buffer = [0, 0]
                lnew, lold = 0, 0
                while stacktop[0] > next_value:
                    buffer[0], buffer[1] = stacktop[0], stacktop[1] + buffer[1]
                    lnew += stacktop[1]
                    area = buffer[0] * buffer[1]
                    (max_area, rect) = (area, [pos - lnew, pos - 1]) if max_area < area else (max_area, rect)
                    if len(stack) > 0:
                        stacktop = stack.pop(len(stack) - 1)                        
                    else:
                        break
                buffer[1] += 1
                buffer[0] = next_value
                if stacktop[0] == next_value:
                    stacktop[1] += buffer[1]
                    stack.append(stacktop)
                elif stacktop[0] < next_value:
                    stack.append(stacktop)
                    stack.append(buffer)
                else:
                    stack.append(buffer)               
                    
        pos += 1
    # empty stack
    lnew = 0
    buffer = [0, 0]
    while len(stack) > 0:
        stacktop = stack.pop(len(stack) - 1)
        buffer[0], buffer[1] = stacktop[0], stacktop[1] + buffer[1]
        area = buffer[0] * buffer[1]
        lnew += stacktop[1]
        (max_area, rect) = (area, [pos - lnew, pos - 1]) if max_area < area else (max_area, rect)
        
    return max_area, rect

w = [0 for n in range(0, len(m[0]))]
max_area = 0
rect = 0
for n in range(0, len(m)):
    for j in range(0, len(m[0])):
        w[j] = w[j] + 1 if m[n][j] == '1' else 0
    area, r = getMaxRectOnRow(w)
    r = [n] + r
    (max_area, rect) = (area, r) if area > max_area else (max_area, rect)
    print w 
    
 print "Found area of ", max_area
print "Rect located at row " , rect[0], " from column ", rect[1], " to column ", rect[2]

public static void main(String[] args)
	{	
		int [][] a = 
				{
			  // 0 1 2 3 4 5 6
		   /*0*/{1,0,0,0,1,0,0}, 
		   /*1*/{0,0,0,0,1,0,0}, 
		   /*2*/{0,0,1,1,1,1,1}, 
		   /*3*/{0,0,1,1,1,1,0}, 
		   /*4*/{0,0,1,1,1,1,0}
				}; 
		int[] cur = {2,2};
		int[] opp = {4,3};
		
		System.out.println(maxarea(a));
		
	}
	
	
	public static int maxarea(int[][] a)
	{
		int max = 0;
		for(int i = 0; i< a.length; i++)
		{
			for(int j = 0; j<a[0].length; j++)
			{
				max = Math.max(max, recusirvemax(a,new int[]{i,j},new int[]{i,j}));
			}
		}
		
		
		return max;
	}
	
	public static int recusirvemax(int[][] a, int[] cur, int[] opp)
	{
		int max = 0;
		if(valid(a,cur,opp))
		{
			if(cur[0]==opp[0] && cur[1]==opp[1])
			{
			  max = 1;
			}
			else
			{
				max = (opp[0]-cur[0]+1)*((opp[1]-cur[1]+1));
				if(max <=1 )
				{
					System.out.println("ERROR");
				}
			}
				
			int[] oppRight = Arrays.copyOf(opp, 2);
			int[] oppDown = Arrays.copyOf(opp, 2);
			oppRight[1]=oppRight[1]+1;
			int moveright =  recusirvemax(a, cur, oppRight);
			oppDown[0]=oppRight[0]+1;
			int movedown =  recusirvemax(a, cur, oppDown);
			int maxchild = Math.max(movedown, moveright);
			max = Math.max(max, maxchild);
		}
		return max;
	}
	
	
	public static boolean valid(int[][] a, int[] cur, int[] opp)
	{
		
		if(cur[0]==opp[0] && cur[1]==opp[1])
		{
			if(a[cur[0]][cur[1]] == 0)
			{
				return false;
			}
			else
			{
				return true;
			}
		}

		if((a.length<=opp[0])||(a[0].length<=opp[1]))
		{
			return false;
		}
		
		
		for(int i = cur[0]; i< a.length && i<=opp[0]; i++)
		{
			for(int j = cur[1]; j <a[0].length &&  j<=opp[1]; j++)
			{
				if(a[i][j]==0)
				{
					return false;
				}
			}
		}
		
		
		return true;
	}

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

/* find the largest rectangle in a histogram */
int largestRectangleInHistogram(const vector<int>& H)
{
    stack<int> S;
    int maxArea = 0;

    for (int i = 0; i < H.size(); i++) {
      while (!S.empty() && H[S.top()] >= H[i])
         S.pop();

      int span = S.empty() ? (i + 1) : (i - S.top());
      maxArea = max(maxArea, span * H[i]);

      S.push(i);
    }

    return maxArea;
}

int largestRectangleInMatrix(const vector<vector<int>>& M)
{
    int rows = M.size();
    int columns = M[0].size();

    vector<int> H(columns);

    for (int j = 0; j < columns; j++)
        H[j] = M[0][j];

    int maxArea = largestRectangleInHistogram(H);

    for (int i = 1; i < rows; i++) {
        for (int j = 0; j < columns; j++)
            H[j] = M[i][j] ? H[j] + 1 : 0;

        maxArea = max(maxArea, largestRectangleInHistogram(H));
    }
    return maxArea;
}
int main()
{
    vector<vector<int>> M = {
        {1,0,0,0,1,0,0},
        {0,0,0,0,1,0,0},
        {0,0,1,1,1,1,1},
        {0,0,1,1,1,1,0},
        {0,0,1,1,1,1,0}
    };

    cout << "max area = " << largestRectangleInMatrix(M) << endl;
}

/* output: max area = 12 */

In my opinion, we simply build a two dimensional array. Each element of the arrays is a struct (x,y)
X represents the number of consecutive ones in the row
Y represents the number of consecutive ones in the column.
F(i,j) = if A(i,j) is 1 then F(i,j) = F(i-1) + 1 , F(j-1) + 1
Once you hit a zero, you initialize the cell to 0,0
Sample Array for the input:
0,0 0,0 0,0 1,0 0,0
1,1 2,1 3,1 0,0 0,0
1,2 2,2 3,2 4,1 0,0
1,3 2,3 0,0 0,0 0,0
1,4 2,4 0,0 1,1 0,0

And then simply doing another loop in the array, multiply the X*Y coordinates and the largest product is your largest triangle. O(n^2)

Stop hacking. Start thinking.
This is a special case of the maximum subarray problem in 2 dimension. see "Efficient algorithms for the maximum subarray problem by distance matrix multiplication" by Takaoka, T. (2002)

python solution with complexity O(height^2 * width)

import random 

def longest_subarray_1D(a):
    ''' a is an array of 0 or 1 
        find the longest contiguous subarray consists of all 1's
        this is a variant of Kadane's algorithm '''

    # initialization
    n = len(a)
    max_j = 0
    begin = [0] * n # [begin[j],j] indicates the optimal subarray ending at j
    if a[0] == 1:
        begin[0] = 0
        max_length = 1
    else:
        begin[0] = 1
        max_length = 0

    # loop through position 1 to n-1
    for j in xrange(1,n):
        if a[j] == 1: 
            if a[j-1] == 1: begin[j] = begin[j-1]
            else: begin[j] = j
        else : begin[j] = j+1
        current_length = j - begin[j] + 1
        if current_length > max_length:
            max_length = current_length
            max_j = j

    # return the start and end position of the optimal subarray
    return (begin[max_j], max_j+1)


def largest_subarray_2D(a):
    ''' taking a horizontal stripe between height y1 and y2
    compute the max-area rectangle in this stripe by 
    collapsing into a 1D problem 
    complexity O(h^2*w), so one improvement is to transpose a so that height < width
    '''

    w = width(a)
    h = height(a)
    max_area =  -1
    max_coordinate = None
    for y1 in xrange(h):
        collapsed = a[y1]
        for y2 in xrange(y1,h):
            # everything inside this loop is O(w)
            collapsed = [collapsed[i]*a[y2][i] for i in xrange(w)]
            begin,end = longest_subarray_1D(collapsed)
            area = (end-begin)*(y2-y1+1)
            if area > max_area:
                max_area = area
                max_coordinate = (y1,y2+1,begin,end)
    return (max_area, max_coordinate)

def width(a):
    return len(a[0])

def height(a):
    return len(a)

def test_longest_subarray_1D():
    a = [random.randint(0,1) for i in xrange(10)]
    print a
    print longest_subarray_1D(a)

def test_largest_subarray_2D():
    w = 4
    h = 5
    a = [[random.randint(0,1) for i in xrange(w)] for j in xrange(h)]
    for row in xrange(height(a)):
        print a[row]
    print 'area, (start_y, end_y, start_x, end_x)'
    print largest_subarray_2D(a)

if __name__ == "__main__":
    test_longest_subarray_1D()
    test_largest_subarray_2D()

I got a solution using dynamic programming techniques, whose complexity is matrix width by height, both runtime and spatial.

Tests first:

//  CSPMaxAreaInMatrixTests.m

#import <XCTest/XCTest.h>
#import "CSPMatrixUtils.h"

@interface CSPMaxAreaInMatrixTests : XCTestCase

@end

@implementation CSPMaxAreaInMatrixTests

- (void)setUp
{
    [super setUp];
    // Put setup code here. This method is called before the invocation of each test method in the class.
}

- (void)tearDown
{
    // Put teardown code here. This method is called after the invocation of each test method in the class.
    [super tearDown];
}

- (void)testOriginalCase
{
    char matrix[5][5] = { { '\0', '\0', '\0', '\1', '\0' },
        { '\1', '\1', '\1', '\0', '\0' },
        { '\1', '\1', '\1', '\1', '\0' },
        { '\1', '\1', '\0', '\0', '\0' },
        { '\1', '\1', '\0', '\1', '\0' } };
    XCTAssertEqual(8, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
                                            withWidth:5 andHeight:5]);
}

- (void)testNullMatrix
{
    unsigned char matrix[5][5] = { { '\0', '\0', '\0', '\0', '\0' },
        { '\0', '\0', '\0', '\0', '\0' },
        { '\0', '\0', '\0', '\0', '\0' },
        { '\0', '\0', '\0', '\0', '\0' },
        { '\0', '\0', '\0', '\0', '\0' } };
    XCTAssertEqual(0, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
                                            withWidth:5 andHeight:5]);
}

- (void)testOneOne
{
    unsigned char matrix[5][5] = { { '\0', '\0', '\0', '\0', '\0' },
        { '\0', '\0', '\0', '\0', '\0' },
        { '\0', '\0', '\0', '\1', '\0' },
        { '\0', '\0', '\0', '\0', '\0' },
        { '\0', '\0', '\0', '\0', '\0' } };
    XCTAssertEqual(1, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
                                            withWidth:5 andHeight:5]);
}

- (void)testAllBlack
{
    unsigned char matrix[5][5] = { { '\1', '\1', '\1', '\1', '\1' },
        { '\1', '\1', '\1', '\1', '\1' },
        { '\1', '\1', '\1', '\1', '\1' },
        { '\1', '\1', '\1', '\1', '\1' },
        { '\1', '\1', '\1', '\1', '\1' } };
    XCTAssertEqual(25, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
                                             withWidth:5 andHeight:5]);
}

- (void)testAllWhite
{
    unsigned char matrix[5][5] = { { '\0', '\0', '\0', '\0', '\0' },
        { '\0', '\0', '\0', '\0', '\0' },
        { '\0', '\0', '\0', '\0', '\0' },
        { '\0', '\0', '\0', '\0', '\0' },
        { '\0', '\0', '\0', '\0', '\0' } };
    XCTAssertEqual(0, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
                                             withWidth:5 andHeight:5]);
}

- (void)testCheckers
{
    unsigned char matrix[5][5] = { { '\0', '\1', '\0', '\1', '\0' },
        { '\1', '\0', '\1', '\0', '\1' },
        { '\0', '\1', '\0', '\1', '\0' },
        { '\1', '\0', '\1', '\0', '\1' },
        { '\0', '\1', '\0', '\1', '\0' } };
    XCTAssertEqual(1, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
                                            withWidth:5 andHeight:5]);
}

- (void)testSecondAndThirdRows
{
    unsigned char matrix[5][5] = { { '\1', '\1', '\1', '\0', '\1' },
        { '\1', '\1', '\1', '\1', '\1' },
        { '\1', '\1', '\1', '\1', '\1' },
        { '\0', '\1', '\1', '\1', '\1' },
        { '\1', '\1', '\0', '\1', '\1' } };
    XCTAssertEqual(12, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
                                             withWidth:5 andHeight:5]);
}

- (void)testSecondToFourthColumns
{
    unsigned char matrix[5][5] = { { '\1', '\1', '\1', '\1', '\0' },
        { '\1', '\1', '\1', '\1', '\1' },
        { '\1', '\1', '\1', '\1', '\1' },
        { '\0', '\1', '\1', '\1', '\1' },
        { '\1', '\1', '\1', '\1', '\1' } };
    XCTAssertEqual(16, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
                                             withWidth:5 andHeight:5]);
}

@end

Header of the solution:

//  CSPMatrixUtils.h

#import <Foundation/Foundation.h>

@interface CSPMatrixUtils : NSObject

/**
 * Given a matrix of ones and zeroes, returns the area of the maximum rectangle
 * composed by ones inside the matrix.
 * @param matrix a matrix of chars
 * @param width the matrix width
 * @param height the matrix height
 * @return the area of the maximum rectangle of ones contained in the matrix
 */
+ (NSUInteger)maxAreaInMatrix:(char*)matrix withWidth:(NSUInteger)width
                    andHeight:(NSUInteger)height;

@end

Implementation (in Objective-C++) using dynamic programming:

//  CSPMatrixUtils.mm

#import "CSPMatrixUtils.h"
#include <math.h>

// For each cell (i, j) in the matrix, we'll keep the max area of ones in the
// submatrix determined by (0, 0) and (i, j), provided that (i, j) is contained
// in that max area.
typedef struct {
    unsigned row, column;   // top/left corner of the max area
    unsigned height, width; // dimensions
} MaxArea;

MaxArea newMaxArea(int row, int col)
{
    MaxArea maxArea{};

    maxArea.row = row; maxArea.column = col;
    maxArea.width = maxArea.height = 1;

    return maxArea;
}

// Given two rectangles, returns a new one as the minimum area that contains
// both rectangles
MaxArea outterArea(MaxArea* leftTopArea, MaxArea* currentArea)
{
    MaxArea outterArea = *currentArea;

    if ((leftTopArea->width > 0) && (leftTopArea->height > 0) &&
        (currentArea->width > 0) && (currentArea->height > 0)) {
        outterArea.row = MIN(leftTopArea->row, currentArea->row);
        outterArea.height = MAX(leftTopArea->row + leftTopArea->height,
                                currentArea->row + currentArea->height)
        - outterArea.row;

        outterArea.column = MIN(leftTopArea->column, currentArea->column);
        outterArea.width = MAX(leftTopArea->column + leftTopArea->width,
                               currentArea->column + currentArea->width)
        - outterArea.column;
    }

    return outterArea;
}

// Given two rectangles, returns the intersection of these
MaxArea innerArea(MaxArea* leftArea, MaxArea* topArea)
{
    MaxArea innerArea{};

    if ((leftArea->width > 0) && (leftArea->height > 0) &&
        (topArea->width > 0) && (topArea->height > 0) &&
        (topArea->row + topArea->height > leftArea->row) &&
        (leftArea->column + leftArea->width > topArea->column)){
        innerArea.row = MAX(leftArea->row, topArea->row);
        innerArea.height = leftArea->row - innerArea.row + 1;

        innerArea.column = MAX(leftArea->column, topArea->column);
        innerArea.width = topArea->column - innerArea.column + 1;
    }

    return innerArea;
}

// Given three areas, returns the largest.
MaxArea maxArea3Way(MaxArea* a1, MaxArea* a2, MaxArea* a3)
{
    NSUInteger area1 = a1->width * a1->height,
    area2 = a2->width * a2->height,
    area3 = a3->width * a3->height;

    return (area1 > area2) ?
    ((area1 > area3) ? *a1 : *a3) :
    ((area2 > area3) ? *a2 : *a3);
}

// Given a cell (i, j), calculates the maximum rectangle of ones in the submatrix
// between (0, 0) and (i, j). Returns the area of that maximum rectangle.
NSUInteger calculateMaxArea(char *currentCell, NSUInteger width, NSUInteger height,
                            MaxArea *maxAreaCurrentCell, int row, int col)
{
    MaxArea maxArea = newMaxArea(row, col), maxAreaTop{}, maxAreaLeft{};

    // the max area on top of the current cell is restricted to the current
    // column, with the height adjusted in one unit to contain the current cell
    if ((row > 0) && (*(currentCell - width) != 0)) {
        maxAreaTop = *(maxAreaCurrentCell - width);
        ++(maxAreaTop.height);
        maxAreaTop.column = col;
        maxAreaTop.width = 1;
    }

    // likewise, the max area on the left of the current cell is the max area for
    // the cell before, but with its height restricted to 1 and its width
    // increased to contain the current cell
    if ((col > 0) && (*(currentCell - 1) != 0)) {
        maxAreaLeft = *(maxAreaCurrentCell - 1);
        ++(maxAreaLeft.width);
        maxAreaLeft.row = row;
        maxAreaLeft.height = 1;
    }

    // finally, if the max area on the cell above current and the cell left to
    // current have some intersection, we try to expand that intersection to
    // the current cell
    if ((row > 0) && (col > 0)) {
        MaxArea inner = innerArea(maxAreaCurrentCell - width,
                                  maxAreaCurrentCell - 1);
        maxArea = outterArea(&inner, &maxArea);
    }

    // the max area will be the max between these three
    *maxAreaCurrentCell = maxArea3Way(&maxArea, &maxAreaLeft, &maxAreaTop);

    return (maxAreaCurrentCell->width) * (maxAreaCurrentCell->height);
}

@implementation CSPMatrixUtils

+ (NSUInteger)maxAreaInMatrix:(char*)matrix withWidth:(NSUInteger)width
                    andHeight:(NSUInteger)height
{
    NSUInteger maxAreaFound = 0;

    // fail-fast: null matrix can't have any area
    if ((width == 0) || (height == 0)) return 0;

    // the spatial complexity is O(width * height)
    MaxArea *maxAreaMatrix = new MaxArea[width * height]();

    MaxArea *maxAreaCurrentCell = maxAreaMatrix;
    char *currentCell = matrix;

    @try {
        // the runtime complexity is O(width * height) as well
        for (int row = 0; row < width; ++row) {
            for (int col = 0; col < height; ++col, ++currentCell, ++maxAreaCurrentCell) {
                if (*currentCell) {
                    // we dinamically calculate the maximum rectangle between
                    // (0, 0) and the current cell, using info from the cell
                    // above and the cell on the left
                    NSUInteger maxAreaForCurrentCell =
                    calculateMaxArea(currentCell, width, height,
                                     maxAreaCurrentCell, row, col);

                    // at all times we keep the maximum area found
                    if (maxAreaForCurrentCell > maxAreaFound) {
                        maxAreaFound = maxAreaForCurrentCell;
                    }
                }
            }
        }
    } @finally {
        delete [] maxAreaMatrix;
    }

    return maxAreaFound;
}

@end

I've approached the problem by constructing possible rectangles convering the upper part of the matrix while scanning it row-by row.

Pseudo code:
1. Extract runs: Extract begin end positions for each all-one substrings on each row.
2. Maintain a set of possible rectangles while consuming runs for each row.
3. Obtain the maximum area from possible rectanges.

In step 2.:
- If the run does not overlap any possible rectangle: create a new rectangle with height 1
- If the run matches a rectangle perfectly: make the rectangle higher.
- If there is partial overlap: Close rectangle, create new rectangle for the overlap, begin new rectange for the run as well.

I belive these cover all possible cases. Can someone find a case where this approach would not work? See the code below.

I belive time complexity is O(n). Space complexity is O(width).

from pprint import pprint

def getruns(row):
	"Do run-length encoding on a single row."
	pos = 0
	begin = None
	for cell in row:
		if cell is 1:
			if begin is None:
				begin = pos
		else:
			if begin is not None:
				yield begin, pos
				begin = None
		pos += 1
	if begin is not None:
		yield begin, pos

def getrects(m):
	"Construct possible rectangles by matching runs of successive rows."
	rects = []
	for row in range(0, len(m)):
		newRects = []
		for begin, end in getruns(m[row]):
			print('run {}:{}-{}'.format(row, begin, end))
			found = False
			for rbegin, rend, height in rects:
				if begin < rend and end > rbegin or begin > rend and end < rbegin:
					newRects.append((max(begin,rbegin), min(end,rend), height+1))
					if rbegin < begin or rend > end:
						yield rbegin, row-height, rend-rbegin, height
					if (begin, end) == (rbegin, rend):
						found = True
				else:
					yield rbegin, row-height, rend-rbegin, height
			if not found:
				newRects.append((begin, end, 1))
		rects = newRects
	for rbegin, rend, height in rects:
		yield rbegin, row-height, rend-rbegin, height

def getmaxarea(m):
	print()
	pprint(m)
	maxArea = 0
	for row, col, w, h in getrects(m):
		print("rect {},{}:{},{} {}*{} = {}".format(row, col, row+w, col+h, w, h, w*h))
		area = w * h
		maxArea = max(maxArea, area)
	print(maxArea)
	return maxArea
	
m = [
	[0,0,0,1,0],
	[1,1,1,0,0], 
	[1,1,1,1,0],
	[1,1,0,0,0],
	[1,1,0,1,0],
]
assert(getmaxarea(m)==8)

n = [
	[1,1,1,1,1],
	[1,1,1,1,1], 
	[1,1,1,1,0],
	[1,1,1,0,0],
	[1,1,0,0,0],
]
assert(getmaxarea(n)==12)

o = [
	[1,1,0,1,1],
	[1,1,1,1,1], 
	[1,1,1,1,0],
	[1,0,1,0,1],
	[1,1,0,1,1],
]
assert(getmaxarea(o)==8)

p = [
	[1,1,1,0,0],
	[1,1,1,0,1], 
	[1,1,1,0,1],
	[0,1,1,1,1],
	[0,1,1,0,0],
]
assert(getmaxarea(p)==10)

Use DP. Maintain an nXm matrix parent where parent[i][j] = least x such that all entries vertically between (x,j) to (i,j) are 1's. Now for a given i, iterate through all contigous series of 1's , updating the area each time. The max area is then returned. You may check you solution at oj.leetcode.com/problems/maximal-rectangle/. Here is my solutio that got accepted. Turn debug to true to see debug messages for more clearity.

class Solution {
public:
	bool debug;
    int maximalRectangle(vector<vector<char> > &matrix) {
        debug = false;
    	int n = matrix.size();
    	if(n==0){
    		return 0;
    	}
    	int m = matrix[0].size();
    	vector<vector<int> > parent(n , vector<int>(m , 0));
    	for(int i=1;i<n;++i){
    		for(int j=0;j<m;++j)if(matrix[i][j]=='1'){
    			if(matrix[i-1][j]=='1'){
    				parent[i][j] = parent[i-1][j];
    			}else{
    				parent[i][j] = i;
    			}
    		}
    	}
    	if(debug){
    		cout<<"Grid : "<<endl;
    		for(int i=0;i<n;++i){
    			for(int j=0;j<m;++j){
    				cout<<matrix[i][j]<<" ";
    			}
    			cout<<endl;
    		}
    		cout<<"=============="<<endl<<"Parent Mat : "<<endl;
			for(int i=0;i<n;++i){
				for(int j=0;j<m;++j){
					cout<<parent[i][j]<<" ";
				}
				cout<<endl;
			}
			cout<<"================="<<endl;
		}
    	
    	int max_a=0 , a , index , p;
    	for(int i=0;i<n;++i){
    		for(int j=0;j<m;++j)if(matrix[i][j]=='1'){
    			if(debug)cout<<"At "<<i<<","<<j<<endl;
    			index = j;
    			p = parent[i][j];
    			while(index>-1 && matrix[i][index]=='1'){
    				p = parent[i][index]<=p ? p : parent[i][index];
    				a = (j-index+1)*(i-p+1);
    				max_a = max_a>a ? max_a : a;
    				if(debug)cout<<"\tindex:"<<index<<" p:"<<p<<" a:"<<a<<" max_a:"<<max_a<<endl;
    				--index;
    			}
    			if(debug)cout<<"================="<<endl;
    		}
    	}
        return max_a;
    }
};

Dinamic Programming, first move be cols calculating the horizontal length,then move by rows calculating the rectangles areas, keep trak of max rectangle. Time O(M) where M is rows * cols

public int FindMaxRectangleArea(int[,] matrix)
{
	var dp = new int[matrix.GetLength(0), matrix.GetLength(1)];
	
	// Calculate/propagate horizontal values
	for (int i=0; i < matrix.GetLength(0); i++)
		for(int j=0; j < matrix.GetLength(1); j++)
			if (matrix[i,j] == 1)
			{
				int prev = (j > 0) ? dp[i,j-1] : 0;
				dp[i,j] = matrix[i,j] + prev;
			}
	
	//Calculate the rectangle areas, propagate vertical and keep track of the maximum area
	int max = 0;
	for (int i=1; i < matrix.GetLength(0); i++)
		for(int j=0; j < matrix.GetLength(1); j++)
			if (matrix[i,j] == 1)
			{
				int prev = (i > 0) ? dp[i-1,j] : 0;
				dp[i,j] += dp[i-1,j];
				max = Math.Max(max, dp[i,j]);
			}
	
	
	return max;
}

prerequisite: largest rectangle in a histogram problem

You can solve this problem using the largest rectangle in a histogram as a suroutine. first make a 2D array where you save the numbers of consecutive 1's that can be seen above starting at the position (i,j) of the matrix of 1s and 0s.
EX:

1 0 1 0
	0 1 1 1
	0 1 1 0
the corresponding 2D array would be
	1 0 1 0
	0 1 2 1
	0 2 3 0

now for each row call the largest rectangle in the histogram subroutine.
considering the example above:

row1:	1
	row2:	3
	row3:	4

the maximum of the 3 rows is 4. thus 4 is the answer

theta(n square) complexity