The below code finds the rectangle with maximum area in a histogram with O(n) time complexity.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | 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++; }} |
