CareerCup

First, consider the following problem (Maximizing Histogram rectangle area problem): Given an array of non-negative integers which represents column heights in a column graph, what is the maximum area rectangle in the given graph?
For instance, suppose array = {1,3,5,2,4,1,3} (first column height is 1, second is 3,...). The maximum area rectangle's height in this case is 2 and its width would be 4 (corresponding to the indices 1,2,3,4 in array).

To solve this problem we'll maintain a stack of array indices with the following constraints:
1. The indices are in increasing order.
2. The column heights which correspond to the stack indices are in a non-decreasing order.

We'll iterate over the array and we'll push indices into the stack as long as conditions (1) and (2) hold. If we've reached a point where we can't push an index without violating constraint (2) then that means that the height of the current column (column i) is smaller than the column whose index is at the top of the stack. In this case, we'll pop indices and compare rectangle areas (with the maximum area) until we can finally push the current index into the stack. The rectangle area at each stage (when we pop) will be calculated by multiplying the popped column height - height(popped_index) and the number of columns between him and the current column (the columns we already popped) - current_index - popped_index. Notice that constraint (1) implies that the column heights of columns between the column at the top of the stack and the current column are all greater/equal to the stack's top column height which implies that the area we calculate is indeed of a rectangle which is included in the column graph.

Here is an implementation of this idea (the method maxHistRect()):

private static class AreaIndices {
		public final int from;
		public final int to;
		public final int height;
		
		public AreaIndices(int from, int to, int height){
			this.from = from;
			this.to = to;
			this.height = height;
		}
		
		public int area(){return (to-from+1)*height;}
		
		@Override
		public String toString(){return "(" + from + "," + to + "," + height + ")";}
	}
	
	private static AreaIndices maxHistRect(int[] histogram){
		if (histogram==null){return null;}
		
		Stack<Integer> stack = new Stack<Integer>();
		AreaIndices res = new AreaIndices(0,0,0);
		int i=0;
		while ((i<histogram.length) || (!stack.isEmpty())){
			if ((stack.isEmpty()) || ((i<histogram.length) && (histogram[i]>=histogram[stack.peek()]))){stack.push(i++);}
			else {
				int cur = stack.pop();
				if (histogram[cur]*(i-cur) >= res.area()){res = new AreaIndices(cur,i-1,histogram[cur]);}
			}
		}
		
		return res;
	}

Now that we know the solution to the Maximum Histogram Rectangle problem, we'll solve the original problem. We'll build an mxn array (assuming the input matrix is mxn) - dp in the following way:
dp[i][j] = 0 if matrix[i][j] == 0
dp[i][j] = 1 + dp[i][j-1] if matrix[i][j] == 1 (I'll consider dp[i][-1] as 0)
The resulting matrix dp is a matrix where dp[i][j] represents the number of consecutive 1's (without 0 in between) in column j which end in row i (including). For instance, if dp[i][j] = 4 then it means that matrix[i][j-3] = matrix[i][j-2] = matrix[i][j-1] = matrix[i][j] = 1.

Here is the code that builds the matrix dp:

private static int[][] buildHistograms(int[][] arr){
		if (arr==null){return null;}
		for (int i=0;i<arr.length;i++){
			if ((arr[0]==null) || ((i>0) && (arr[i].length != arr[i-1].length))){return null;}
		}
		
		int m = arr.length,n = arr[0].length;
		int[][] dp = new int[m][n];
		for (int i=0;i<dp.length;i++){
			for (int j=0;j<dp[i].length;j++){
				dp[i][j] = (arr[i][j]==0) ? 0 : 1 + ((i>0) ? dp[i-1][j] : 0);
			}
		}
		
		return dp;
	}

After building the matrix dp, we can look at each row dp[i] in this matrix as a column graph (the height in this case is the number of consecutive 1's in each column ending in the row i). We already know how to find the maximum area rectangle in a column graph.

For instance, suppose we found that the maximum area rectangle for dp[i] has height of h and corresponds to columns k,k+1,...,l. By the definition of dp we conclude that our matrix has the following rectangle: start_row = i-h+1, end_row = i, start_column = k, end_column = l.

All that's left is to find the maximum rectangle for every row dp[i] and to take the maximum between all of them (getMaxOnesRectange()):

public static class RectangleCoordinates {
		public final int rowFrom;
		public final int rowTo;
		public final int colFrom;
		public final int colTo;
		
		public RectangleCoordinates(int rowFrom, int rowTo, int colFrom, int colTo){
			this.rowFrom = rowFrom;
			this.rowTo = rowTo;
			this.colFrom = colFrom;
			this.colTo = colTo;
		}
		
		@Override
		public String toString(){
			return "Rows: " + rowFrom + "-" + rowTo + ", Columns: " + colFrom + "-" + colTo;
		}
	}
	
	public static RectangleCoordinates getMaxOnesRectange(int[][] arr){
		if (arr==null){return null;}
		
		int[][] dp = buildHistograms(arr);
		if (dp==null){return null;}
		AreaIndices max = null;
		RectangleCoordinates res = null;
		
		for (int i=0;i<dp.length;i++){
			AreaIndices cur = maxHistRect(dp[i]);
			if ((max==null) || (max.area()<cur.area())){
				max = cur;
				res = new RectangleCoordinates(i-cur.height+1,i,cur.from,cur.to);
			}
		}
		
		return res;
	}

This solution is O(m*n) run-time and space. It also finds the maximum area rectangle consisting from 1's. It is easy to use it to find the maximum area rectangle consisting from 0's as well (just apply it to the matrix with all elements switched from 0 to 1 and from 1 to 0).

It worked for the couple of tests I ran but I didn't test it too thoroughly.

static int FindLargestOnes(bool[,] table, int width, int height, out int x, out int y, out int w, out int h)
{
int currentmax = 0;
int[,] maxw = new int[height, width];
int[,] maxh = new int[height, width];
x = y = w = h = 0;
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++)
{
if (table[i, j])
{
if (i == 0 && j == 0)
{
maxw[i, j] = maxh[i, j] = 1;
}
else if (j == 0)
{
maxw[i, j] = 1;
maxh[i, j] = maxh[i - 1, j] + 1;
}
else if (i == 0)
{
maxw[i, j] = maxw[i, j - 1] + 1;
maxh[i, j] = 1;
}
else
{
maxw[i, j] = maxw[i, j - 1] + 1;
maxh[i, j] = maxh[i - 1, j] + 1;
if (maxw[i - 1, j] - maxw[i, j - 1] <= 1)
{
int tmpw = maxw[i - 1, j];
int tmph = maxh[i - 1, j] + 1;
if (tmpw * tmph > maxw[i, j] * maxh[i, j])
{
maxw[i, j] = tmpw;
maxh[i, j] = tmph;
}
}
if (maxh[i, j - 1] - maxh[i - 1, j] <= 1)
{
int tmpw = maxw[i, j - 1] + 1;
int tmph = maxh[i, j - 1];
if (tmpw * tmph > maxw[i, j] * maxh[i, j])
{
maxw[i, j] = tmpw;
maxh[i, j] = tmph;
}
}
}
if (maxw[i, j] * maxh[i, j] > currentmax)
{
w = maxw[i, j];
h = maxh[i, j];
x = j - w + 1;
y = i - h + 1;
currentmax = w * h;
}
}
}
return currentmax;
}

#include <cstdlib>
#include <iostream>

//Given a 2D array of 1 and 0, Find the largest rectangle (may not be square) which is made up of all 1 or 0.

using namespace std;

#ifdef HISTOGRAM
int hist[4] = {3,2,6,8};
void find(int i)
{
     int j = i;
     int sz =0;
   
     while(hist[i] <= hist[j])
     {
        //cout << "hist[i]" << hist[i] << " i " << i << "  hist[j]" << hist[j] << " j " << j << endl;
        sz = sz + hist[i];
        if( j == 3 )
             break;
        j++;
     }
     cout << i << "th=" << sz << endl; 
}


int main(int argc, char *argv[])
{
    
    for(int i = 0; i<4 ; i++)
    {
      find(i);
            
            
    }
    
    
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

#endif



int hist[4][4] = 
                 {
                   {0,1,1,1},
                   {1,1,1,1},
                   {1,0,1,0},
                   {1,0,0,0},
                  };
void print(const int& j,const int& i)
{
    int szx = 0;
    int szy = 0;
    int y = 0;
    int x = 0;
    bool ff = true;
    while(hist[x + i][y + j] == hist[i][j] && y < 4)
    {

        while(hist[x + i][y + j ] == hist[i][j] && x < 4)
        {
          x++;                 
        }
        if (ff)
         szx = x ;
        else if(szx > x )
        szx = x ;
         ff = false;
        szy++;
        y++;
        x = 0;
       // cout << "--y--" << endl;
    }
    
      
      cout << "i,j = (" << i << " , " << j << " ) sz = (" << szx << " , "<< szy   << " )" << endl;           
}
    
 

int main(int argc, char *argv[])
{
    
    for(int i = 0; i < 4 ; i++)
    {
      for(int j = 0; j < 4 ; j++)      
      {
            print (i,j);
 
            
      }
      
    }
   // cout << hist[1][2];
    system("PAUSE");
    return EXIT_SUCCESS;
}

DP solution provided on StackOverflow.com. Put 1726632 in search there (CC doesn't allow links in the answers). In essence this is an algorithm:

At each scan do this:

If the cell has 0 assign count=0
If the cell has 1 and is an edge cell (bottom or right edge only), assign count=1
For all other cells, check the count of the cell on its right, right-below, and below. Take the min of them and add 1 and assign that to the count. Keep a global max_count variable to keep track of the max count so far.

Here is good solution id=15420704.
The other one is here.
belbesy.wordpress.com/2011/03/11/uva-108-maximum-sum/