I believe this problem requires checking every possible height of the rectangle. I've come up with something like below, that seems to be an improvement:
6!:2 'a =: maxsq arr' 0.860414 6!:2 'b =: >./,(+**@[)/\.|:(*<:/~) arr' 4.47701 a -: b 1 NB. maxsq: find the maximum square over the set of each unique height NB. nsq: max square of height x: mark positions where the height exceeds the value, determine the maximum length of uninterrupted sequence by subtracting adjacent positions, get square by multiplying to the height chosen ceilpos =: ceilpos =: 0: , (I.@:>) , (#@:]) maxbitlen =: 13 : '<: >./ 2-~/\y' nsq =: ([* maxbitlen@:ceilpos)"0 1 maxsq =: ([:>./ ~.nsq])f. arr =: 10000?.1000000 2017-06-20 23:43 GMT+03:00 Raul Miller <rauldmil...@gmail.com>: > Hmm... maybe I should have just gone out and shown how I approached > the problem... > > (but feel free to hold off on reading this post, or replies to it, if > you are wanting to solve it on your own and you think you understand > the problem description). > > And, perhaps, I should add that that drdobbs writeup is a more general > problem than the one I'm proposed. There you start with a boolean > array, instead of a list of bar lengths. > > So, anyways, we need some kind of representation of which bars are > lower than which other bars. Something like this: > > <:/~2 6 7 4 1 7 > 1 1 1 1 0 1 > 0 1 1 0 0 1 > 0 0 1 0 0 1 > 0 1 1 1 0 1 > 1 1 1 1 1 1 > 0 0 1 0 0 1 > > Next, to calculate area, we'll need to know how high each of those bar > representations are. We can get that by multiplying each length by the > corresponding "relevant height" bits: > > (* <:/~)2 6 7 4 1 7 > 2 2 2 2 0 2 > 0 6 6 0 0 6 > 0 0 7 0 0 7 > 0 4 4 4 0 4 > 1 1 1 1 1 1 > 0 0 7 0 0 7 > > Now we just need to add them up, stopping when we hit a zero. We could > use a rank 1 scan, but since our operation is going to be a bit > complex maybe it makes more sense to work on the transpose of that > array: > > |: (* <:/~)2 6 7 4 1 7 > 2 0 0 0 1 0 > 2 6 0 4 1 0 > 2 6 7 4 1 7 > 2 0 0 4 1 0 > 0 0 0 0 1 0 > 2 6 7 4 1 7 > > Now... when building up a scan, it's worth starting with a > representative pair of arguments and figuring out what operation we > want on them. In other words something to go in the parenthesis, here: > > 0 0 0 0 1 0 () 2 6 7 4 1 7 > > Given our description of adding them up and stopping at zeros, I went > with (+ * *@[) > > 0 0 0 0 1 0 (+ * *@[) 2 6 7 4 1 7 > 0 0 0 0 2 0 > > In other words: > > (+ * *@[)/\. |: (* <:/~)2 6 7 4 1 7 > 8 0 0 0 6 0 > 6 12 0 12 5 0 > 4 6 7 8 4 7 > 2 0 0 4 3 0 > 0 0 0 0 2 0 > 2 6 7 4 1 7 > > We can see all the various rectangle areas here, and we just need to > find the largest: > > >./ , (+ * *@[)/\. |: (* <:/~)2 6 7 4 1 7 > 12 > > Now... that works reasonably well up to a point, but time and space > are proportional to the square length of the list of bar lengths. > > In other words, this is reasonably fast: > > >./ , (+ * *@[)/\. |: (* <:/~) 1000?.1000000 > 7030779 > > ... but this is not so fast: > > >./ , (+ * *@[)/\. |: (* <:/~) 10000?.1000000 > 9694475 > > Anyways, I believe that it should be possible to solve this quite a > bit more quickly, but I have not worked out how yet. > > Thanks, > > -- > Raul > > > On Tue, Jun 20, 2017 at 1:03 PM, Joe Bogner <joebog...@gmail.com> wrote: > > possible spoiler - > > http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529 > > > > At a minimum, it help explains the problem > > > > > > > > On Tue, Jun 20, 2017 at 1:02 PM, Xiao-Yong Jin <jinxiaoy...@gmail.com> > > wrote: > > > >> Brute force: > >> > >> (\:*/"1);<@:((#,<./)\.)\2 6 7 4 1 7 > >> 2 6 > >> 3 4 > >> 4 2 > >> 2 4 > >> 1 7 > >> 1 7 > >> 1 6 > >> 3 2 > >> 6 1 > >> 5 1 > >> 5 1 > >> 2 2 > >> 1 4 > >> 4 1 > >> 4 1 > >> 3 1 > >> 3 1 > >> 1 2 > >> 2 1 > >> 2 1 > >> 1 1 > >> > >> Though the complexity looks like n^3 to me. There must be a more > >> efficient algorithm. > >> > >> > On Jun 20, 2017, at 10:29 AM, Raul Miller <rauldmil...@gmail.com> > wrote: > >> > > >> > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
