From: Doug Coleman <doug.coleman@gmail.com>
Date: Fri, 22 Oct 2021 18:45:31 +0000 (-0500)
Subject: sequences.extras: Add Kadane's algorithm for finding the maximum sum
X-Git-Tag: 0.99~2254
X-Git-Url: https://gitweb.factorcode.org/gitweb.cgi?p=factor.git;a=commitdiff_plain;h=9dc82158a698d5346dceadecaf16a8cdc80ef11a

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 69b02869a8..f4ede8fb24 100644
--- 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 b8d8eb89d7..994939d881 100644
--- 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 ;