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
