sequences.extras: Add Kadane's algorithm for finding the maximum sum

of consecutive elements from a sequence.

diff --git a/extra/sequences/extras/extras-tests.factor b/extra/sequences/extras/extras-tests.factor
index 69b02869a8376f7e602bfc18080f5fe1295fba52..f4ede8fb2461113a0d9827044cc6d234b45adafc 100644 (file)
--- a/extra/sequences/extras/extras-tests.factor
+++ b/extra/sequences/extras/extras-tests.factor
@@ -271,3 +271,8 @@ tools.test vectors vocabs ;
 
 { 25 5 1 } [ { 4 5 6 } [ sq ] [ 20 > ] find-pred ] unit-test
 { f f f } [ { 4 5 6 } [ sq ] [ 200 > ] find-pred ] unit-test
+
+{ -1/0. } [ { } max-subarray-sum ] unit-test
+{ -2 } [ { -3 -2 } max-subarray-sum ] unit-test
+{ 7 } [ { 1 2 3 -4 5 } max-subarray-sum ] unit-test
+{ 6 } [ { 1 2 3 -4 1 1 } max-subarray-sum ] unit-test

diff --git a/extra/sequences/extras/extras.factor b/extra/sequences/extras/extras.factor
index b8d8eb89d79f17bd1816912f40844b7c7e33b5fc..994939d881db3f5e01b62bee841ebe067c5ceef5 100644 (file)
--- a/extra/sequences/extras/extras.factor
+++ b/extra/sequences/extras/extras.factor
@@ -661,3 +661,9 @@ PRIVATE>
     [ 0 ] 3dip
     [ [ length check-length ] keep ] 2dip
     '[ nth-unsafe _ keep swap _ keep swap ] find-pred-loop swapd ; inline
+
+! https://en.wikipedia.org/wiki/Maximum_subarray_problem
+! Kadane's algorithm O(n) largest sum in subarray
+: max-subarray-sum ( seq -- sum )
+    [ -1/0. 0 ] dip
+    [ [ + ] keep max [ max ] keep ] each drop ;