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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#!/usr/bin/perl
#
# Task 2: "Largest Rectangle Histogram
#
# 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"
#
# My notes: hmm.. so max(area of all rectangles "in" a histogram). But what does that mean?
# Hang on: the "graphs" are NOT actually histograms: each is simply the array of values itself.
# So forgot frequency hashes. The simplest way that I can see is to calculate the area of all
# possible rectangles (where 1 or more adjacent values are at least some minimum height) and
# then to find the maximum of all those.
#
use strict;
use warnings;
use feature 'say';
use Function::Parameters;
use Data::Dumper;
use List::Util qw(max);
die "Usage: largest-histogram-rect values\n" if @ARGV==0;
#
# my @areas = rectangleareasofheight( $h, @value );
# Find all rectangle areas of height $h in @value. Returns an array of
# one or more numbers (each area).
#
fun rectangleareasofheight( $h, @value )
{
# want to locate runs of adjacent values >= $h, each such run has
# a width, that w * h is the area. use a 2-state state machine:
# state 0 is: not currently in such a run.
# state 1 is: currently in such a run, $area is the current area of the run.
my @result;
my $state = 0;
my $area = 0;
foreach my $v (@value)
{
#say "debug: state=$state, v=$v, h=$h, area=$area";
if( $state == 0 && $v>=$h )
{
# enter state 1, start counting the area
$state=1; $area=$h;
} elsif( $state == 1 && $v>=$h )
{
# stay in state 1: increase the area
$area+=$h;
} elsif( $state == 1 && $v<$h )
{
# finish one run, revert to state 0
push @result, $area;
#say "height $h: run area: $area, back to state 0 at value $v";
$state = 0; $area = 0;
}
}
# final possible extra area..
if( $state == 1 )
{
push @result, $area;
#say "height $h: run area: $area";
}
return @result;
}
#
# my @areas = allrectangleareas( @value );
# Find all rectangle areas of @value. Works by checking each height
# separately.
#
fun allrectangleareas( @value )
{
my @result;
my $maxv = max @value;
foreach my $h (1..$maxv)
{
#say "looking for rectangles of height $h";
push @result, rectangleareasofheight($h,@value);
}
return @result;
}
my @values = @ARGV;
my @areas = allrectangleareas( @values );
#say Dumper \@areas;
my $max = max @areas;
say $max;
|
