Question: Find the maximum rectangle enclosed by the
following barchart:
____
12
|
| |
10
|
| |
8
| ___
| |-----
6 | ___|
|
___|
|___
4 | |
|
|__|
|____________
2 | |
|
|
|
0
--------------------------------------------------------------------------
Solution: public class Main {
public static void main(String[] args)
throws Exception {
List<Integer> A = Arrays.asList(4, 6, 2, 4, 12, 7, 4,2,2,2);
System.out.println(getMaxRectangleStreaming(A));
}
public static int
getMaxRectangleStreaming(List<Integer> A) {
int maxArea =
Integer.MIN_VALUE;
int maxHeight
= Integer.MIN_VALUE;
List<Integer> heights = new ArrayList<>();
// parallel
sums of unit-areas of bounding boxes with top-left at incremental heights of
the current bar in a barchart
List<Integer> areas = new ArrayList<>();
int prev =
0;
for (int i =
0; i < A.size(); i++) {
if (A.get(i) > maxHeight) {
maxHeight = A.get(i);
}
if (prev < A.get(i)) {
for (int j = 0; j < A.get(i); j++) {
if (heights.size() < j+1) heights.add(0);
if (areas.size() < j+1) areas.add(0);
heights.set(j, (j+1) * 1);
if ( j < areas.size()) {
int newArea = areas.get(j) + (j + 1) * 1;
areas.set(j, newArea);
if (newArea > maxArea) {
maxArea = newArea;
}
} else {
areas.set(j, (j+1) * 1);
}
}
} else {
for (int j = 0; j < A.get(i); j++) {
heights.set(j, (j+1) *1);
if ( j < areas.size()) {
int newArea = areas.get(j) + (j + 1) * 1;
areas.set(j, newArea);
if (newArea > maxArea) {
maxArea = newArea;
}
} else {
areas.set(j, (j+1) * 1);
}
}
for (int j = A.get(i); j < prev; j++){
heights.set(j, 0);
if (areas.size() > j && areas.get(j) > maxArea) {
maxArea = areas.get(j);
}
areas.set(j, 0);
}
}
prev = A.get(i);
System.out.println("heights:" + print(heights));
System.out.println("areas:" + print(areas));
}
return
maxArea;
}
public static String
print(List<Integer> A){
StringBuilder
sb = new StringBuilder();
for (Integer a
: A) {
sb.append(a + " ");
}
return
sb.toString();
};
}
//Output:
heights:1 2 3 4
areas:1 2 3 4
heights:1 2 3 4 5 6
areas:2 4 6 8 5 6
heights:1 2 0 0 0 0
areas:3 6 0 0 0 0
heights:1 2 3 4 0 0
areas:4 8 3 4 0 0
heights:1 2 3 4 5 6 7 8 9 10 11 12
areas:5 10 6 8 5 6 7 8 9 10 11 12
heights:1 2 3 4 5 6 7 0 0 0 0 0
areas:6 12 9 12 10 12 14 0 0 0 0 0
heights:1 2 3 4 0 0 0 0 0 0 0 0
areas:7 14 12 16 0 0 0 0 0 0 0 0
heights:1 2 0 0 0 0 0 0 0 0 0 0
areas:8 16 0 0 0 0 0 0 0 0 0 0
heights:1 2 0 0 0 0 0 0 0 0 0 0
areas:9 18 0 0 0 0 0 0 0 0 0 0
heights:1 2 0 0 0 0 0 0 0 0 0 0
areas:10 20 0 0 0 0 0 0 0 0 0 0
20
No comments:
Post a Comment