Put comments in Kadane's algo and added functional version in Ruby

jcla1 · jcla1 · commit b81a3f6c4d47 · 2014-01-01T12:16:45.000+01:00
diff --git a/Maximum_Subarray/Ruby/jcla1/maximum_subarray.rb b/Maximum_Subarray/Ruby/jcla1/maximum_subarray.rb
@@ -5,10 +5,24 @@ def maximum_subarray(arr)
 
     cur_max, max_so_far = arr.first, arr.first
 
+    # arr[1..-1] is getting everything,
+    # but the first element of the array.
+    # It is equivalent to (cdr arr) in Lisp/Scheme etc.
     arr[1..-1].each do |v|
         cur_max = [cur_max+v, v].max
         max_so_far = [cur_max, max_so_far].max
     end
 
+    # Ruby automatically returns the last evaluated
+    # expression, so we've no need for return
     max_so_far
+end
+
+
+def maximum_subarray_functional(arr)
+    # This is the functional one-liner of Kadane's algorithm
+    # The accumulator in reduce is an array containing:
+    # [0] - maximum sum so far
+    # [1] - current maximum streak
+    arr[1..-1].reduce([arr[0], arr[0]]) { |mem, n| c = [n, mem[1]+n].max; [[mem[0], c].max, c] }[0]
 end
