algorithm - “Finding Maximum Sum of Subsequent Elements”算法分析

Question

如果可能的话，我希望有人对算法给出分析解释。

例如给定序列

-2, 4, -1, 3, 5, -6, 1, 2 

最大的子序列和是

4 + -1 + 3 + 5 = 11

我指的这个算法是一个分而治之的算法。

该算法的复杂度为O(nlogn)。

实际上，我想查看该算法生成的所有步骤的示例。上面的序列可以用于示例。

Answer 1

这个想法是将你的序列分成两半，找到两半的答案，然后用它来找到整个序列的答案。

假设您有一个序列[left, right]。让 m = (left + right)/2。现在，[left, right] 的最大和子序列 (MSS) 是 MSS(left, m), MSS( m + 1, right) 或从 [left, m] 开始并在 [m + 1, right] 某处结束的序列。

伪代码:

MSS(left, right)
  if left = right then return sequence[left]
  m = (left + right) / 2
  leftMSS = MSS(left, m)
  rightMSS = MSS(m + 1, right)

  maxLeft = -inf // find the maximum sum subsequence that ends with m and starts with at least left
  cur = 0
  i = m
  while i >= left do
    cur += sequence[i]
    if cur > maxLeft
      maxLeft = cur

  maxRight = -inf // find the maximum sum subsequence that starts with m + 1 and ends with at most right
  cur = 0
  i = m + 1
  while i <= right
    cur += sequence[i]
    if cur > maxRight
      maxRight = cur

  return max(leftMSS, rightMSS, maxLeft + maxRight)

这是 O(n log n) 因为递归三的高度为 O(log n) 并且在树的每一层我们做 O( n) 工作。

这是它在 -2, 4, -1, 3, 5, -6, 1, 2 上的运行方式:

 0  1  2 3 4  5 6 7
-2  4 -1 3 5 -6 1 2

                                             MSS(0, 7) = 11
                                      /                    \
                              MSS(0, 3) = 6                 MSS(4, 7) = 5 ------
                          /                  \              |                   \
           MSS(0, 1) = 4                    MSS(2, 3) = 3   MSS(4, 5) = 5      NSS(6, 7) = 3
             /       \                    /              \
   MSS(0, 0) = -2     MSS(1, 1) = 4    MSS(2, 2) = -1    MSS(3, 3) = 3

有趣的是 MSS(0, 3) 和 MSS(0, 7) 的计算，因为它们不只是取其子项的最大值。对于 MSS(0, 3)，我们尝试从间隔 (1) 的中间开始向左添加连续的元素，从而获得尽可能大的总和。这个最大值是 4。接下来我们做同样的事情，从区间的中间 + 1 开始，然后向右走。这个最大值是 2。将它们相加得到一个总和为 6 的最大和子序列，它大于两个子区间的最大和子序列，所以我们取这个。

MSS(0, 7) 的推理类似。