“求后续元素的最大和”的分析；算法

Question

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

例如，给定序列，

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

最大子序列和将是

4 + -1 + 3 + 5 = 11

我所指的这个算法是分而治之类型的算法。

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

实际上，我希望看到该算法产生的所有步骤的示例。上述序列可用于该示例。

Answer 1

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

假设您有一个序列[left, right]。让m =（左+右）/ 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) 的计算code> 和 MSS(0, 7)，因为它们并不简单地取其子代的最大值。对于 MSS(0, 3)，我们尝试通过从间隔 (1) 的中间开始并向左添加连续元素来获得尽可能大的总和。该最大值为 4。接下来，我们从间隔 + 1 的中间开始并向右进行相同的操作。该最大值为2。将它们加在一起得到一个总和为 6 的最大和子序列，它大于两个子区间的最大和子序列，所以我们取这个。

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

Answer 2

这实际上可以使用名为 Kadane 算法 的算法在 O(n) 时间内完成。如果您有兴趣，我已经写了我自己的版本及其复杂性分析 。这个想法是使用动态规划来逐步改进解决方案，直到找到最佳子序列。