Might be worth adding to https://rosettacode.org/wiki/Greatest_subsequential_sum#J ?
Thanks, — Raul On Sunday, February 24, 2019, 'Jon Hough' via Programming < [email protected]> wrote: > Reference: https://en.wikipedia.org/wiki/Maximum_subarray_problem > > This is the problem: > Given an array of numbers, find the contiguous subset of maximum sum. i.e. > find the maximum sum subarray. > Example: > R=: 3 4 _5 2 1 1 > The maximum subarray is 3 4 > > Kadane's algorithm is a linear time algorithm to solve this. Rather than > explicitly implementing this, I wanted a J verb to solve this, using J > primitives. > > I wrote a horrendously long one-liner to solve this: > f=: ({.@:I.@:(= >./)@:>@:({:&.>) { ])@:(>:@:i.@:# (({.@:I.@:(= >./) ([ , > {) ])@:(+/\) <@,~ [)"0 _ ]) ((i.@:{. + {:)@:}:@:,@:>@:[ { ]) ] > > Empirically, I found this to be O(n) in time. e.g. > For an array of length 8000 > timespacex gives: 0.25468 3.40134e6 > For array of length 16000: 1.03293 6.80102e6 > For array of length 32000: 4.09139 1.36004e7 > For array of length 64000: 16.3896 2.71991e7 > > Any better solutions (faster, and more elegant)? > > Thanks, > Jon > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
