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

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

例如，给定顺序

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

最大子序列和为

4 + -1 + 3 + 5 = 11

我引用的该算法是分治式的算法。

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

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

最佳答案

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

假设您有一个序列[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)类似。

关于algorithm - “Finding Maximum Sum of Subsequent Elements”算法分析，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6837496/