1 files changed, 6 insertions, 0 deletions

diff --git a/lib/Utils.hs b/lib/Utils.hs
index 1381f16..61c4e49 100644
--- a/lib/Utils.hs
+++ b/lib/Utils.hs
@@ -43,3 +43,9 @@ sublists = concatMap inits . tails
 
 windows :: Int -> [a] -> [[a]]
 windows m = foldr (zipWith (:)) (repeat []) . take m . tails
+
+kadane :: [Int] -> Int
+kadane = go 0 0
+    where go :: Int -> Int -> [Int] -> Int
+          go best _ [] = best
+          go best current (l:ls) = go (max best (current + l)) (max current (current + l)) ls