CareerCup

Look at: w/w/w/.homeofcox-cs.blogspot.com/2010/04/max-rectangle-in-histogram-problem.html

could you elaborate the question, max are under given rectangle? what rectangle? and how is the rectangle represented?

Start from lowest left corner and go right one by one, putting sums to the block 1,2 3. Go up to second level and do the same but cells will go like 2,4,6 since they have blocks under them. 3rd level will have 3 6 9,and so on. Choose the block with largest sum and go to the left till there are no cells on the left and you have your rectangle. If i understand the question correctly :)

We can use divide and conquer approach.

Let h[] be the array and kth element be the minimum element in h[] from index i to j

max_area = max(max_area(i, k-1), max_area(k+1, j), h[k]*(j-i))

i will be set to 0 and j will be set to array length initially

What does question say ?

what does Max Area mean? The highest value in the histogram that this rectangle area ovrlaps with?

Question doesn't make sense the way it is stated right now.

Question doesn't make sense the way it is stated right now.

Working C++ code:

int MaxRectangleAreaHistogram(vector <int> HistogramVec, unsigned int length, int width, int MaxHeight)
{
if (length >= HistogramVec.size()) // processed all histograms
{
return 0;
}
int HistHeight = HistogramVec[length];

if (MaxHeight > HistHeight) //prev recursive call does not apply to this
{
return 0;
}

int sum = 0;
int maxSum = 0 ;

if (MaxHeight < 0 ) {
maxSum = HistogramVec[length];
sum = MaxRectangleAreaHistogram(HistogramVec, length + 1, width, -1);

if (sum > maxSum) {
maxSum = sum;
}

for (int i=0; i <HistHeight ;i++)
{
sum = (i+1)*width + MaxRectangleAreaHistogram(HistogramVec, length + 1, width, i+1);
if (sum > maxSum) {
maxSum = sum;
}
}
}
else
{
sum = MaxHeight + MaxRectangleAreaHistogram(HistogramVec, length + 1, width, MaxHeight);
if (sum > maxSum) {
maxSum = sum;
}
}

return maxSum;
}

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

int DEBUG = 1;

//
// Note that if s->size() becomes 0, then left = start.
// This is useful when entry in hist[] can be zero.
// If all entries in hist[] are positive, then no need to use start,
// In that case, use -1 in place of start in this function.
//
void getMax(int hist[], stack<int> * s,
            int newHeight, int right, int & max, int & start)
{
    int height, left = 0, area;
    while (s->size() > 0 && hist[s->top()] > newHeight)
    {
        height = hist[s->top()];
        s->pop();
        left = (s->size() > 0) ? s->top() : start;
        while (s->size() > 0 && hist[s->top()] == height)
        {
            s->pop();
            left = (s->size() > 0) ? s->top() : start;
        }

        area = height * (right - left);
        if (DEBUG) cout<<"\narea: "<<height<<"*("<<right<<"-"<<left<<") = " <<area;
        if (area > max) max = area;
    }

}

//
// Note that when hist[i] == top_v, we push i.
// In the acm judge site, it says skip i if equal.
// But I feel somehow it can't keep track of the left value
// when multiple columns have the same height.
//
int doHist(int hist[], int len)
{
    stack<int> * s = new stack<int>;
    int i, max, top_v;
    int start = -1; // the position before the last 0, used by left.

    max = 0;
    for (i = 0; i < len; i ++)
    {
        if (s->size() == 0)
        {
            s->push(i);
            continue;
        }

        top_v = hist[s->top()];
        if (hist[i] >= top_v)
        {
            s->push(i);
        }
        else if (hist[i] < top_v)
        {
            getMax(hist, s, hist[i], i - 1, max, start);
            s->push(i);
            if (hist[i] == 0) start = i - 1;
        }
    }

    getMax(hist, s, 0, i - 1 , max, start);

    cout << "\nmax = " << max << endl;
    return max;
}

int main()
{
    //int hist[] = {3, 5, 4, 7, 6, 5, 2}; // answer: 20
    int hist[] = {1,2,1};
    doHist(hist, sizeof(hist) / sizeof(int));
    return 0;
}

for every i do
1. if stack empty then push i i.e. create subpoblem
2. if hist[i] >= top element in stack, push(i) i.e. create subproblem
3. if hist[t] < top element in stack,
a. solve all subproblems existing in stack and popping them off until the top most element in stack is less than the current hist[i]
b. push i, i.e. create subproblem

now solve the remaining subproblems in stack by sending an element of height 0 and width i-1

A good explanation with figures tech-queries.blogspot . com /2011/03/ maximum-area-rectangle-in-histogram.html

O(n) solution ; implemented the algorithm for this question found on stackoverflow

from collections import namedtuple
from collections import deque

Info=namedtuple('Info','start height')

def max_rectangle_area(histogram):
    pos=0
    max_area=0
    stack=[]
    top=lambda:stack[-1]
    for pos,height in enumerate(histogram):
        start=pos
        while True:
            if not stack or top().height < height:
                stack.append(Info(start,height))
            elif stack and top().height > height:
                max_area=max(max_area,top().height*(pos-top().start))
                start,_=stack.pop()
                continue
            break
    pos+=1

    for start,height in stack:
        max_area=max(max_area,height*(pos-start))
    return max_area

if __name__=='__main__':
    histogram=[4,8,3,1,1,0]
    print max_rectangle_area(histogram)

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

w..w.w..w.w.wtech-queries.blogspot.in/2011/03/maximum-area-rectangle-in-histogram.html

import java.util.PriorityQueue;

public class MaxAreaRectangle {

	class HeightAndPosition implements Comparable<HeightAndPosition> {
		int height, position;
		
		public HeightAndPosition(int height, int position) {
			this.height = height;
			this.position = position;
		}

		@Override
		public int compareTo(HeightAndPosition arg0) {
			return height - arg0.height;
		}
	}
	
	public MaxAreaRectangle() {
	}

	public int evaluate(int[] a){
		
		int n = a.length;
		int[] heights = new int[n+1];
		for(int i = 0; i < n; i++){
			heights[i] = a[i];
		}
		heights[n] = 0;
		
		PriorityQueue<HeightAndPosition> activeRectangles = new PriorityQueue<HeightAndPosition>();
		
		int maxArea = 0;
		for(int i = 0; i < n; i++){
			if(activeRectangles.size() > 0 && activeRectangles.peek().height >= heights[i]){
				// update all rectangles that get closed now
				int minLeftIndex = i;
				while(activeRectangles.size() > 0 && activeRectangles.peek().height >= heights[i]){
					HeightAndPosition e = activeRectangles.poll();
					// close rectangle
					int area = (i - e.position)*e.height;
					maxArea = Math.max(maxArea, area);
					
					minLeftIndex = Math.min(minLeftIndex, e.position);
				}
				HeightAndPosition e = new HeightAndPosition(heights[i],minLeftIndex);
				activeRectangles.add(e);
			} else {
				HeightAndPosition e = new HeightAndPosition(heights[i],i);
				activeRectangles.add(e);
			}
		}
		
		return maxArea;
	}
	

	public static void main(String[] args){
		   MaxAreaRectangle wrapper = new MaxAreaRectangle();
		   int[] testcase = { 7 , 4 , 4 , 2 , 3 };
		   
		   int c = wrapper.evaluate(testcase);
		   System.out.println("cost " + c);
	   }
}