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.stream());
}
public static int
getMaxRectangleStreaming(BaseStream<Integer> stream) {
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;
Iterator<Integer> iterator = stream.iterator();
While(iterator.hasNext()){
Integer a = iterator.Next();
if (a > maxHeight) {
maxHeight = a:
}
if (prev < a) {
for (int j = 0; j < a; 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; 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; 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;
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