最早知道「最大区间和问题」好像是看 Udi Manber 的《算法引论》。最近又在 @吴军 的《计算之魂》1.3 节中看到。
nums = %w[1.5 -12.3 3.2 -5.5 23.2 3.2 -1.4 -12.2 34.2 5.4 -7.8 1.1 -4.9].map { |e| e.to_f }
)
算法
def max_sum_1(ary)
n = ary.size
max_sum = 0
b, e = 0, 0
n.times do |p|
(p...n).each do |q|
# s = ary[p..q].sum
# 为便于分析算法性能，还是用 for 循环更清晰一些：
s = 0
ary[p..q].each { |e| s += e }
if s > max_sum
max_sum = s
b, e = p, q
end
end
end
[max_sum, [b, e]]
end
p max_sum_1(nums) #=> [52.4, [4, 9]]
)
算法
def max_sum_2(ary)
n = ary.size
max_sum = 0
b, e = 0, 0
n.times do |p|
partial_sum = 0 # 保存 ary[p..(q - 1)].sum
(p...n).each do |q|
# puts "#{p} .. #{q}"
s = partial_sum + ary[q]
if s > max_sum
max_sum = s
b, e = p, q
end
partial_sum = s
end
end
[max_sum, [b, e]]
end
p max_sum_2(nums)
))
分治算法
def max_sum_3_using_divide_and_conquer(ary, b, e)
return [ary[b], [b, e]] if b == e
# -----b_l----e_l----------(mid)---------b_r---------e_r-----➡️
mid = (b + e) / 2
max_sum_l, interval = max_sum_3_using_divide_and_conquer(ary, b, mid)
b_l, e_l = interval
max_sum_r, interval = max_sum_3_using_divide_and_conquer(ary, mid + 1, e)
b_r, e_r = interval
if e_l + 1 == b_r
if max_sum_l > 0 and max_sum_r > 0
return [max_sum_l + max_sum_r, [b_l, e_r]]
else
if max_sum_l > max_sum_r
return [max_sum_l, [b_l, e_l]]
else
return [max_sum_r, [b_r, e_r]]
end
end
else
maybe_sum = max_sum_l + ary[(e_l + 1)..(b_r - 1)].sum + max_sum_r
sum2p = {
maybe_sum => [b_l, e_r],
max_sum_l => [b_l, e_l],
max_sum_r => [b_r, e_r]
}
larger_sum = [maybe_sum, max_sum_l, max_sum_r].max
return [larger_sum, sum2p[larger_sum]]
end
end
p max_sum_3_using_divide_and_conquer(nums, 0, nums.size - 1)
终极皇冠👑：)
线性算法
@吴军 说是用「正、反两遍扫描」，但理解起来太费劲。其实用递归也能解释（先不考虑边界情况）：
- 找到第一个为正
+的数，再找
-的数。计算出
；
- 递归寻找
段上的最大区间和，记为
，同时顺道求出
；
- 剩下的就是常规操作了：
，意味着排除掉
，需要在
中选择。
，意味着只需在
中选择。
不过坑🕳️还是很多的，昨晚调试到凌晨两点🕑😖。
def find_the_first_positive_num(ary, b = 0)
l = nil
sum_before_l = 0
ary[b..].each_with_index do |e, i|
if e >= 0
l = b + i
break
end
sum_before_l += e
end
if l.nil? # 全为负。
return [nil, nil]
else
return [l, sum_before_l]
end
end
def find_the_first_negative_num(ary, b = 0)
l = nil
sum_before_l = 0
ary[b..].each_with_index do |e, i|
if e < 0
l = b + i
break
end
sum_before_l += e
end
if l.nil? # 全为正。
return [nil, nil]
else
return [l, sum_before_l]
end
end
def max_sum_4(ary, b, e, depth = 0)
# return format: [sum_before_l, [l..r], max_sum]
return [0, [b, e], ary[b]] if b == e if b == e
p0, sum_left_side_0 = find_the_first_positive_num(ary, b)
if p0.nil? # 全为负数。
max_negative = ary[b..e].max
idx = ary.index(max_negative)
return [0, [idx, idx], max_negative]
else
l, r, max_sum = nil
q0, sum_p0 = find_the_first_negative_num(ary, p0)
if q0.nil?
return [ary[b...p0].sum, [p0, e], ary[p0..e].sum] if q0.nil? # [p0 .. e] 全为正数。
else
sum_left_side, interval, max_sum_rest = max_sum_4(ary, q0, e, depth)
l_rest, r_rest = interval
return [sum_left_side_0, [p0, q0 - 1], sum_p0] if max_sum_rest < 0
if sum_p0 + sum_left_side >= 0
if sum_left_side + max_sum_rest >= 0
# 扩展至 [p0 .. r_rest]
return [sum_left_side_0, [p0, r_rest], sum_p0 + sum_left_side + max_sum_rest]
else
# 只保留 [p0 .. q0 - 1]
return [sum_left_side_0, [p0, q0 - 1], sum_p0]
end
else
if sum_p0 >= max_sum_rest
return [sum_left_side_0, [p0, q0 - 1], sum_p0]
else
return [sum_left_side_0 + sum_p0 + sum_left_side, [l_rest, r_rest], max_sum_rest]
end
end
end
end
end
p max_sum_4(nums, 0, nums.size - 1)
网友评论