[Jprogramming] largest rectangle problem

[Louis de Forcrand]

Let V be a vector of real numbers, and V[i] its ith component.
Then

min( V[i] … V[j+1] ) = min( min( V[i] … V[j] ), min( V[i+1] … V[j+1] ) ).

This version is based on that:

   ms=: #\ >./ . * [: >./@> # 2&(<./\&.>)&< ]
   1e3 ts 'ms qq'
0.00491435 5.74234e6

Incorporating this in Mike's explicit version with an early stopping condition
could lead to even faster runtimes!

Cheers,
Louis

> On 25 Jun 2017, at 11:00, 'Mike Day' via Programming <programming at jsoftware.com> wrote:
> 
> There must be something about breakfast.
> A loopy stopping condition has just presented itself.  Others might see a tacitisation:
> 
> cs =: 3 : 0
> 
> m =. >./y
> 
> for_i. }.>:i.n =. #y do.
> 
> m =. m >. q =. >./ i ([ * <./\) y
> 
> if. (m * i) >: n * q do. break. end.
> 
> end.
> 
> m
> 
> )
> 
> q holds the maximum area at "width" i . No subsequent area
> 
> can be greater than q*n%i where n is the maximum width, so
> 
> stop if that is no greater than the current maximum, m.
> 
> It's twice as fast and uses slightly less space than c, the loopy verb
> 
> without an early stopping condition:
> 
> ts'c qq'
> 
> 0.014258 21632
> 
> ts'cs qq'
> 
> 0.0044897 21504
> 
> ts'C qq' NB. Raul's best tacit version - so far...
> 
> 0.00803071 289920
> 
> Now for lunch,
> 
> Mike
> 
> 
> On 24/06/2017 20:09, Raul Miller wrote:
>> True, except that if you did not have the inner >./ the "0 1 would not help.
>> 
>> Thanks,
>> 
> 
> 
> 
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm