"寻找后续元素最大和"算法的分析

Question

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

例如,给定序列

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

最大子序列总和

4 + -1 + 3 + 5 = 11

我正在考虑的这个算法是一种分而治之的算法.

该算法是O(nlogn)复杂度.

实际上,我试图看到该算法产生的所有步骤的示例.上述序列可用于该示例.

Answer 1

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

假设您有一个序列[left, right]。让m = (left + right) / 2。现在， 的最大和子序列 ( MSS)[left, right]要么是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)。