I like the scanl concept from haskell scanl =: \.(&.|.) < scanl i.4 +-+---+-----+-------+ |0|1 0|2 1 0|3 2 1 0| +-+---+-----+-------+
The advantage of using the scanl solution below is that you also easily get the location of the ending index that gives the maximum sum. Its not much slower. ts '>./ (0>. +)/\. y' 0.00594102753319 67712 >./ (0>. +)/ scanl y 18 ts '>./ (0>. +)/ scanl y' 0.0107060647528 133888 end index of maximum sum: (i.>./) (0>. +)/ scanl y 10 ----- Original Message ---- From: ramacd <[EMAIL PROTECTED]> To: Programming forum <[email protected]> Sent: Tuesday, April 17, 2007 10:37:19 AM Subject: Re: [Jprogramming] maximum running sum - understanding scan revisited Mike; Bravo on discovering that insight. The page on ostermiller.org was #2 on a Google search for "maximum running sum" so, note to self, Google is your friend. Mike Day wrote: > Hacking away at yet another MathsChallenge problem, > (see http://projecteuler.net/index.php?section=about) > I needed an efficient verb for finding the maximum > running sum of an array. I seem to have stumbled on > a really good one, which surprisingly appears to be > better than Eugene's J version of a K verb mentioned > in the correspondence below. Eugene's article is > also available online at > http://www.jsoftware.com/jwiki/Doc/Articles/Play152 > > [Mathschallengers - this was for problem 149. You > might wish to ignore the details below!] > > Apologies to the K group for the verbosity, but > I'm trying to cover three languages here. > > Given Eugene's example vector: > x =: 31 _41 59 26 _53 58 97 _93 _23 84 > define two verbs: > mrs =: >./@(- <./\)@(+/\) NB. max run sum > NB. ie max over (element - min so far) of cumulative sum > > NB. cf Eugene MacDonell's max infix sum ... > mis =: [: >./ [: (0 >. +)/\. 0 ,~ ] > (mrs,mis) x NB. same answer > 187 187 > > Timing for 10000 elements > y=:10000$0 _3 8 _1 _8 2 5 _5 5 3 8 0 _10 _5 _1 _4 4 _10 _4 _6 > (mrs-:mis) y > 1 > Time & Space > >ts each ('mrs y');'mis y' > 9.4146e_5 197440 > 0.00611307 132288 > > Here's a K version: > kmrs=:{|/{x-&\x}0+\x} / new K max run sum NB. K version > f : |/0(0|+)\ / EM's quoted K function > y: 0 -3 8 -1 -8 2 5 -5 5 3 8 0 -10 -5 -1 -4 4 -10 -4 -6 > \t do[1000;f 10000#y] / time for 1000 applications of f on 10000 elts > of y > 2954 > \t do[1000;kmrs 10000#y] 100 > > And a Dyalog APL Dfn: > y <- 10000 rho 0 -3 8 -1 -8 2 5 -5 5 3 8 0 -10 -5 -1 -4 4 -10 -4 -6 > {{max/w-min\w}+\w} y @ "max" "min" and "w" are APL symbols > 18 @ time it using compare (cmpx) function: > cmpx'{{max/w-min\w}+\w}y ' @ > 10x slower than J & K! {{max/w-min\w}+\w}y 6.7E¯4 > I discovered this independently a couple of days ago, but > must confess to finding that someone had got there before: > http://ostermiller.org/calc/sum.html, > according to his description of his algorithm. > Hardly surprising, though that I couldn't see anything > better in recent J K or APL discussion group messages. > > Mike > > > back in October 2007, Eugene McDonnell wrote: >> >> On Oct 16, 2006, at 3:00 PM, Miller, Raul D wrote: >> >>> I wrote: >>>> (0 >. +)/&.|.\ a >>>> >>>> / is right to left, but gambler uses left to right. >>>> /(&.|.) is left to right. >>> >>> &. is unnecessary and could cause problems in the general >>> case (not this specific case). As & is sufficient, I should >>> have said: >>> >>> (0 >. +)/&|.\ a >>> >>> and so on. >>> >>> -- Raul >> >> The At Play With J article in Vector 15.2, October 1998, has a >> discussion of what it calls "Maximum Infix Sums" which may pertain to >> this problem. >> ---------------------------------------------------------------------- >> 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 Get news delivered with the All new Yahoo! Mail. Enjoy RSS feeds right on your Mail page. Start today at http://mrd.mail.yahoo.com/try_beta?.intl=ca ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
