从「最大区间和问题」看算法的精进

最早知道「最大区间和问题」好像是看 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)

终极皇冠👑： 线性算法

@吴军 说是用「正、反两遍扫描」，但理解起来太费劲。其实用递归也能解释（先不考虑边界情况）：

1. 找到第一个为正 + 的数 ，再找 之后第一个为负 - 的数 。计算出 ；
2. 递归寻找 段上的最大区间和，记为 ，同时顺道求出 ；
3. 剩下的就是常规操作了：
   ，意味着排除掉 ，需要在 中选择。
   ，意味着只需在 中选择。

不过坑🕳️还是很多的，昨晚调试到凌晨两点🕑😖。

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)