Greatest subsequential sum: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 2,185: / Line 2,185: @@
 =={{header|Ruby}}==
+===Brute Force:===
-Answer is stored in "slice":
+Answer is stored in "slice". It is very slow O(n**3)
-<lang ruby>Infinity = 1.0/0
-def subarray_sum(arr)
+<lang ruby>def subarray_sum(arr)
-  max, slice = -Infinity, []
+  max, slice = 0, []
-  arr.each_with_index do |n, i|
+  arr.each_index do |i|
     (i...arr.length).each do |j|
-      sum = arr[i..j].inject(0) { |x, sum| sum += x }
+      sum = arr[i..j].inject(0, :+)
-      if sum > max
+      max, slice = sum, arr[i..j]  if sum > max
-        max = sum
-        slice = arr[i..j]
-      end
     end
   end
   [max, slice]
 end</lang>
+'''Test:'''
+<lang ruby>[ [1, 2, 3, 4, 5, -8, -9, -20, 40, 25, -5],
+  [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1],
+  [-1, -2, -3, -4, -5],
+  []
+].each do |input|
+  puts "\nInput seq: #{input}"
+  puts "  Max sum: %d\n   Subseq: %s" % subarray_sum(input)
+end</lang>
+{{out}}
+<pre>
+Input seq: [1, 2, 3, 4, 5, -8, -9, -20, 40, 25, -5]
+  Max sum: 65
+   Subseq: [40, 25]
+Input seq: [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]
-A better answer would run in O(n) instead of O(n^2) using numerical properties to remove the need for the inner loop.
+  Max sum: 15
+   Subseq: [3, 5, 6, -2, -1, 4]
+Input seq: [-1, -2, -3, -4, -5]
+  Max sum: 0
+   Subseq: []
+Input seq: []
+  Max sum: 0
+   Subseq: []
+</pre>
+===Linear Time Version:===
+A better answer would run in O(n) instead of O(n**2) using numerical properties to remove the need for the inner loop.
 <lang ruby># the trick is that at any point
@@ Line 2,208: / Line 2,233: @@
 # added to it, then do so.
 # the interesting part is proving the math behind it
-Infinity = 1.0/0
 def subarray_sum(arr)
-  curr,max = -Infinity,-Infinity
+  curr = max = 0
-  first,last,curr_first= 0,0,0
+  first, last, curr_first = arr.size, 0, 0
   arr.each_with_index do |e,i|
-    curr = e + curr
+    curr += e
-    if(e>curr)
+    if e > curr
       curr = e
-      curr_first=i
+      curr_first = i
     end
-    if(curr > max)
+    if curr > max
       max = curr
-      last=i
+      first = curr_first
-      first=curr_first
+      last = i
     end
   end
-  return max,arr[first...last+1]
+  return max, arr[first..last]
-end
+end</lang>
+The test result is the same above.
-input=[1,2,3,4,5,-8,-9,-20,40,25,-5]
-p subarray_sum(input)
-=>[65, [40, 25]]
-input=[-3, -1]
-p subarray_sum(input)
-=>[-1, [-1]]</lang>
 =={{header|Run BASIC}}==