OK, Jon - I looked at wiki and implemented Kadane, with mxsasum
(explicit) and mxsasumt (tacit)
returning just the best sum, while mxsa returns the subarray.
NB. Kadane's algorithm as presented in wiki
NB. def max_subarray(A):
NB. max_ending_here = max_so_far = A[0]
NB. for x in A[1:]:
NB. max_ending_here = max(x, max_ending_here + x)
NB. max_so_far = max(max_so_far, max_ending_here)
NB. return max_so_far
NB. returns maximal subarray sum only, not subarray
mxsasum =: 3 : 0
mxeh =. mxsf =. {. a =. y
for_x. }.a do.
mxeh =. x + 0 >. mxeh
mxsf =. mxsf >. mxeh
end.
)
NB. first pass at a tacit form of the above - a bit rough!
NB. bolts on mxeh and mxsf to the front of }. of array
NB. and then works through until no array left...
mxsasumt =: ({.`(((2&{+0>.{.)>./\@:,(1&{)),3&}. ) @.(2<#))^:_@: (,~{.)
NB. returns maximal subarray - only the last if more than one!
mxsa =: 3 : 0
mxeh =. mxsf =. {. a =. y
ii =. i =. j =. 0
for_x. }.a do.
ii =. >: ii
i =. (ii, i) {~ ok =. 0 < mxeh
mxeh =. x + ok * mxeh
j =. (ii, j) {~ ok =. mxeh < mxsf
mxsf =. ok { mxeh, mxsf
end.
NB. could just return i,j !
a {~ i ([ + i.@>:@-~ ) j
)
Some timings
ts
6!:2 , 7!:2@]
q =: 8000$3 4 _5 2 1 1 1
ts'mxsasum q'
0.0168 68672
ts'mxsasumt q'
0.11534 1.25056e6
ts'mxsa q'
0.0590112 134144
ts'f q' NB. Jon's one-liner
0.696457 1.74189e6
ts'>./;(+/\)\. q' NB. NOT THE WAY TO DO IT!
1.98149 8.82859e8
>./;(+/\)\. q
8001
mxsasum q
8001
I very much doubt the book is closed on this one!
Mike
On 24/02/2019 11:39, 'Jon Hough' via Programming 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
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
