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 <[email protected]> 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 <[email protected]> > 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 <[email protected]> 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
