Module: KadaneSan

Defined in:
lib/kadane_san.rb,
lib/kadane_san/version.rb

Constant Summary collapse

VERSION = 
"0.1.0"

Class Method Summary collapse

Class Method Details

.max_subarray(a) ⇒ Object 



4
5
6
7
8
9
10
11
 
# File 'lib/kadane_san.rb', line 4

def self.max_subarray(a)
  max_so_far = max_ending_here = -1.0 / 0
  a.each do |i|
    max_ending_here = [i, max_ending_here + i].max
    max_so_far = [max_so_far, max_ending_here].max
  end
  max_so_far
end

.min_subarray(a) ⇒ Object 



13
14
15
16
17
18
19
20
 
# File 'lib/kadane_san.rb', line 13

def self.min_subarray(a)
  min_so_far = min_ending_here = 1.0 / 0
  a.each do |i|
    min_ending_here = [i, min_ending_here + i].min
    min_so_far = [min_so_far, min_ending_here].min
  end
  min_so_far
end