CareerCup

http www informatik.uni-ulm.de/acm/Locals/2003/html/judge dot html

have a look at the largest rectangle(part H)

Finding max area in Histogram. I haven't ever solve this problem so didn't have much understanding. I can think of only O(n^2) solution.

A classic solution exists using a stack in O(n) time. Google it.

could someone post the solution using stack?...or atleast explain it here

int rectArea = 0;
int arr[5] = {10, 20, 30, 50, 40};

for (int i = 0; i < 5; i++)
{
if ( ((i + 1) * arr[i]) > rectArea)
rectArea = (i + 1) * arr[i];
}

cout << "largest rectangle is " << rectArea << endl;

// this solves in O(n)

int rectArea = 0;
int arr[5] = {10, 20, 30, 50, 40};

for (int i = 0; i < 5; i++)
{
if ( ((i + 1) * arr[i]) > rectArea)
rectArea = (i + 1) * arr[i];
}

cout << "largest rectangle is " << rectArea << endl;

// this solves in O(n)

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    /* invariant: maxendinghere and maxsofar are accurate
       are accurate for x[0..i-1] */
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)

Hi below code uses concept of range minimum query. And time complexity for below code is n(logn).

#include<iostream>
using namespace std;
void initialize(int node,int b,int e,int *M,int *A,int n)
{
if(b==e)
M[node]=b;
else{
initialize(2*node,b,(b+e)/2,M,A,n);
initialize(2*node+1,(b+e)/2+1,e,M,A,n);
if(A[M[2*node]]<=A[M[2*node+1]])
M[node]=M[2*node];
else
M[node]=M[2*node+1];
}
}
int query(int node,int b,int e,int *M,int *A,int i,int j)
{
int p1,p2;
if(i>e || j<b)
return -1;
if(b>=i && e<=j)
return M[node];
p1=query(2*node,b,(b+e)/2,M,A,i,j);
p2=query(2*node+1,(b+e)/2+1,e,M,A,i,j);
if(p1==-1)
return M[node]=p2;
if(p2==-1)
return M[node]=p1;
if(A[p1]<=A[p2])
return M[node]=p1;
return M[node]=p2;
}
long long fun(int i,int j,int *M,int *A,int n)
{
int k;
long long a1=0,a2=0,a3=0;
if(i>j)
return 0;
if(i==j)
return A[i];
k=query(1,0,n-1,M,A,i,j);
a1=(long long)A[k]*(j-i+1);
if(i<=k-1)
a2=fun(i,k-1,M,A,n);
if(k+1<=j)
a3=fun(k+1,j,M,A,n);
if(a1<a2)
a1=a2;
if(a1<a3)
a1=a3;
return a1;
}
int main()
{
int n,i,j;
while(1){
cout<<"enter number of elements";
scanf("%d",&n);
if(n==0)
break;
int A[n+5],M[1000000];
cout<<"enter element";
for(i=0;i<n;i++)
scanf("%d",&A[i]);
initialize(1,0,n-1,M,A,n);
cout<<fun(0,n-1,M,A,n)<<"\n";
if(1) break;
}
return 0;
}

Excellent solution here: http tech-queries.blogspot.com/2011/03/maximum-area-rectangle-in-histogram.html

this problem is similar to maximum subsequence sum problem...with only difference in way we compute the sum.

this problem is similar to maximum subsequence sum problem...with only difference in way we compute the sum.

/*RMQ-> Range minimum query is feasible in O(1) time with linear preprocessing*/
/*Reductions applied - RMQ -> LCA on cartesian tree -> RMQ on a list of tree depths */
/* Time Complexity of below program = O(n) */
/* Space Complexity (used in RMQ)  =O(n) */

/*global variable*/
int max_area=0;


void max_histogram_area(int [] arr,int st,int end)
{
int range_min=RMQ(arr,st,end);
area =(end-st)*range_min;
if(area>max_area) max_area=area;
int diff=end-st;

if(diff>0)
{
partition_1=diff/2;
partition_2=diff/2+1;
max_histogram_area(arr,st,partition_1);
max_histogram_area(arr,st,partition_1);
}

}

for(i=0;i<arr.length;i++)
{
if(arr[i]>currmax)
{
currmax=arr[i];
}
}
this solves in O(n)