“找到连续元素最大和”算法分析

Question

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

例如，给定序列：

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

最大子序列和将会是：

4 + -1 + 3 + 5 = 11

我所指的算法是一种分治算法。

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

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

- Vaios Argiropoulos

---

你的意思是要找到最大的连续子序列和吗？最大子集合和很简单：把所有负数元素都去掉即可。 - Ted Hopp

@Peter - 那只是更多的代码。OP想要对其复杂性进行分析。 - Ted Hopp

使用我提供的序列进行分析性示例即可。 - Vaios Argiropoulos

标题中无需添加“请”或“我想要”。如果你表述清晰并且问题结构良好，那么会得到不错的回答。 - hugomg

好的，缺失编号，我会记住的。 - Vaios Argiropoulos

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) 的推理类似。

- IVlad

---

钉子在头上。我的错误是，在计算基本情况的值时，我排除了一些值，但似乎不应该这样做。谢谢。 - Vaios Argiropoulos

Answer 2

使用一种称为Kadane算法的算法，实际上可以在O(n)的时间内完成此操作。卡丹算法 可以找到一个最优子序列并进行动态规划来逐步改善解决方案。

我自己编写了版本并分析了其复杂性，如果您有兴趣。请注意保留HTML标记。

- templatetypedef

---

我知道O(n)（以及O(n^2)和O(n^3)也存在），但今天我正在学习O(nlogn)算法，所以我需要一个关于这个特定算法的例子。 - Vaios Argiropoulos

这是一份作业任务吗？目前看来你好像在乞求答案，而没有做任何自己的工作。我可以提供分析，但除非我有保证你不只是让我替你完成作业，否则我不会这样做。 - templatetypedef

没有作业。我正在独立地研究算法、离散数学等方面，这是出于自己的兴趣。我有自我激励能力。我已经卡在这个问题上一整天了。我不想看分析，因为我已经找到了很多相关资料。但我还没有找到一个实际序列步骤的例子。 - Vaios Argiropoulos

也许如果您指出您想要分析的具体算法，有人可以为您指引一下分析方法。 :) - Ted Hopp

@Ted Hopp，这里是www.cs.ru.nl/~chaack/teaching/CIS500s00/Transpar/trans15.pdf。在第4页上，您可以看到这个算法。 - Vaios Argiropoulos