The below code finds the rectangle with maximum area in a histogram with O(n) time complexity.
public static void maxRectArea(int a[], int b[]) {
// this is a maximization problem
// irrespective of the height of the the next bar
// we have to compare the area if including next bar exceeds the current area then we have to include the bar.
// stop the expansion and proceed further until end of input.
// 6 2 5 4 5 1 6
// 6 2 5 8 12 1 6
int i = 0;
int max = -1;
int e = 0;
while (i < a.length) {
if (i == 0)
e = b[i] = a[i];
else {
if (a[i] < a[i-1]) {
int t = b[i-1] / e;
if (((t+1) * a[i]) < b[i-1])
e = b[i] = a[i];
else {
e = a[i];
b[i] = (t+1) * a[i];
}
}
else if (a[i] == a[i-1]) {
b[i] = b[i-1] + e;
}
else if (a[i] > a[i-1]) {
if ((b[i-1] + e) > a[i]) {
b[i] = b[i-1] + e;
}
else {
e = b[i] = a[i];
}
}
}
i++;
}
}
No comments:
Post a Comment