[Jprogramming] largest rectangle problem

[Martin Kreuzer]

@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
><programming at jsoftware.com> wrote:
> > is the answer to your example, 6x2 or 4x3?
>
>
>
> > ________________________________
> > From: Raul Miller <rauldmiller at gmail.com>
> > To: Programming forum <programming at jsoftware.com>
> > 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