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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#!/usr/bin/env perl
# Challenge 075
#
# TASK #2 > Largest Rectangle Histogram
# Submitted by: Mohammad S Anwar
# You are given an array of positive numbers @A.
#
# Write a script to find the largest rectangle histogram created by the given
# array.
#
# BONUS: Try to print the histogram as shown in the example, if possible.
#
# Example 1:
#
# Input: @A = (2, 1, 4, 5, 3, 7)
# 7 #
# 6 #
# 5 # #
# 4 # # #
# 3 # # # #
# 2 # # # # #
# 1 # # # # # #
# _ _ _ _ _ _ _
# 2 1 4 5 3 7
# Looking at the above histogram, the largest rectangle (4 x 3) is formed by
# columns (4, 5, 3 and 7).
#
# Output: 12
#
# Example 2:
#
# Input: @A = (3, 2, 3, 5, 7, 5)
# 7 #
# 6 #
# 5 # # #
# 4 # # #
# 3 # # # # #
# 2 # # # # # #
# 1 # # # # # #
# _ _ _ _ _ _ _
# 3 2 3 5 7 5
# Looking at the above histogram, the largest rectangle (3 x 5) is formed by
# columns (5, 7 and 5).
#
# Output: 15
use Modern::Perl;
use List::Util qw( max );
my @A = @ARGV;
my @hist = make_histogram(@A);
my $max_area = max_area(@hist);
say $max_area;
sub make_histogram {
my(@a) = @_;
my $max = max(@a);
my @hist;
for my $c (0 .. $#a) {
for my $r (0 .. $max-1) {
$hist[$r][$c] = $r>=$a[$c] ? 0 : 1;
}
}
return @hist;
}
sub max_area {
my(@hist) = @_;
my $max_area = 0;
for my $r0 (0 .. @hist-1) {
for my $c0 (0 .. @{$hist[$r0]}-1) {
if ($hist[$r0][$c0]) {
for my $height (1 .. @hist-$r0) {
for my $width (1 .. @{$hist[$r0]}-$c0) {
my $all_ones = 1;
for my $r ($r0 .. $r0+$height-1) {
for my $c ($c0 .. $c0+$width-1) {
if (!$hist[$r][$c]) {
$all_ones = 0;
}
}
}
if ($all_ones) {
$max_area = max($max_area, $width*$height);
}
}
}
}
}
}
return $max_area;
}
|
