@Raul
Beg your pardon for taking your time ...
This is what I did (as an approach); maybe I learn something from you
(or somebody else) proving me wrong.
Anyway, this seems to work on the given set of data:
Taking the mean of the column heights
] v=. 2 6 7 4 1 7
2 6 7 4 1 7
am=. +/ % #
am v
4.5
gives a "compacted" rectangle of 4.5 times 6 (base) = 27 units of area.
IIf I 'floor' the mean
] mf=. <. am v
4
and take a look at which columns exceed (the floor of ) the mean I
get this matrix
v,:mf<: v
2 6 7 4 1 7
0 1 1 1 0 1
Here I got stuck with my coding, so I will describe in words only
what I intend to do further on:
* Extract the indices of the largest (longest) block of 1s (1..3) and
calculate its length (3)
* Within that block search for the lowest column value (4)
* Multiply block length (3) with lowest column value within that
range (4) to obtain a rectangle area of 3*4 = 12 units.
Thanks for your patience.
-M
At 2017-06-20 16:07, you wrote:
Both of those are valid answers.
The problem is simply to determine the largest area.
Thanks,
--
Raul
On Tue, Jun 20, 2017 at 11:58 AM, 'Pascal Jasmin' via Programming
<[email protected]> wrote:
> is the answer to your example, 6x2 or 4x3?
> ________________________________
> From: Raul Miller <[email protected]>
> To: Programming forum <[email protected]>
> Sent: Tuesday, June 20, 2017 11:30 AM
> Subject: [Jprogramming] largest rectangle problem
> Something I stumbled over today.
> If we have a series of bars of varying height, what's the largest
> rectangle that can be drawn over the bars without covering any empty
> space.
> For example:
> '*'#"0~2 6 7 4 1 7
> **
> ******
> *******
> ****
> *
> *******
> I'll post a solution later, and I'll be interested in seeing if it's
> basically the only obvious approach or if there's a variety of good
> approaches. (I have reason to believe, though, that there's a better
> way than what I came up with.)
> Thanks,
> --
> Raul
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
