algorithm - 理解递归/子问题如何组合(最大子数组算法)

Question

我在理解分而治之算法时遇到一些问题。我读过，为了成功地应用递归，你需要有一个“递归信仰的飞跃”，你不应该为每一步的细节而烦恼，但我并不真正满足于仅仅接受递归在所有情况下都有效。条件已满足，因为此刻对我来说这似乎很神奇，我想了解它为何有效。

因此，我得到了以下在伪代码中查找最大子数组的递归算法:

Find-Maximum-Subarray(A, low, high)
if high == low
    return (low, high, A[low])
else
    mid = [(low + high)/2]
    (left-low, left-high, left-sum) = Find-Maximum-Subarray(A, low, mid)
    (right-low, right-high, right-sum) = Find-Maximum-Subarray(A,mid + 1, high)
    (cross-low, cross-high, cross-sum) = Find-Max-Crossing-Subarray(A,low, mid, high)
    if left-sum >= right-sum and left-sum >= cross-sum
        return (left-low, left-high, left-sum)
    else if right-sum >= left-sum and right-sum >= cross-sum
        return (right-low, right-high, right-sum)
    else
        return (cross-low, cross-high, cross-sum)

其中 Find-Max-Crossing-Subarray 算法由以下伪代码给出:

Find-Maximum-Crossing-Subarray(A, low, mid, high)
left-sum = -INF
sum = 0
for i = mid down to low
    sum = sum + A[i]
    if sum > left-sum
        left-sum = sum
        max-left = i
right-sum = -INF
sum = 0
for j = mid + 1 to high
    sum = sum + A[j]
    if sum > right-sum 
        right-sum = sum
        max-right = j
return (max-left, max-right, left-sum + right-sum)

现在，当我尝试将此算法应用于示例时，我很难理解所有步骤。

数组被“分解”(使用索引，而不实际更改数组本身)，直到高值等于低值。我认为这对应于第一次调用，因此首先对数组左侧的所有项调用 Find-Maximum-Subarray，直到 high==low==1。然后返回 (low, high, A[low])，在本例中为 (1, 1, A[1])。现在我不明白在调用的其余部分如何处理这些值。

此外，我不明白该算法实际上如何比较长度 > 1 的子数组。请有人向我解释一下，一旦该函数的某个调用触底，该算法将如何继续？

Answer 1

简而言之:
令 A 为长度为 n 的数组。您想要计算 A 的最大子数组，因此您调用 Find-Maximum-Subarray(A, 0, n-1)。现在尝试让问题变得更简单:

1. 案例。高=低:
   在这种情况下，数组只有 1 个元素，因此解决方案很简单

2. 高!=低
   在这种情况下，解决方案很难找到。所以尽量把问题变小。如果我们将数组 A 切成一半长度的数组 B1 和 B2 会发生什么。现在只有3例新增病例

   a) A 的最大子数组也是 B1 的子数组，但不是 B2
   b) A 的 max 子数组也是 B2 的子数组，但不是 B1
   c) A 的最大子数组与 B1 和 B2

   重叠

   因此，您分别计算 B1 和 B2 的最大子数组，并寻找重叠的解决方案，最后取最大的一个。

现在的窍门是，您可以使用 B1 和 B2 做同样的事情。

示例:

A =[-1, 2, -1, 1]
Call Find-Maximum-Subarray(A, 0, 3);
 - Call Find-Maximum-Subarray(A, 0, 1); -> returns ( 1, 1, 2 )  (cause 2 > 1 > -1,  see the subcalls)
    - Call Find-Maximum-Subarray(A, 0, 0); -> returns ( 0, 0, -1 )
    - Call Find-Maximum-Subarray(A, 1, 1); -> returns ( 1, 1, 2 )
    - Call Find-Max-Crossing-Subarray(A, 0, 0, 1); -> returns ( 0, 1, 1 )
 - Call Find-Maximum-Subarray(A, 2, 3); -> returns ( 3, 3, 1 ) ( 1 > 0 > -1, see subcalls)
    - Call Find-Maximum-Subarray(A, 2, 2); -> returns ( 2, 2, -1 )
    - Call Find-Maximum-Subarray(A, 3, 3); -> returns ( 3, 3, 1 )
    - Call Find-Max-Crossing-Subarray(A, 2, 2, 3); returns ( 2, 3, 0 )
 - Call Find-Max-Crossing-Subarray(A, 0, 1, 3); -> returns ( 1, 3, 2 )
    - Here you have to take at least the elements A[1] and A[2] with the sum of 1, 
      but if you also take A[3]=1 the sum will be 2. taking A[0] does not help 
      due to A[0] is negative
 - Now you have only to look which subarray has the larger sum. In this case you 
   have two with the same size: A[1] and A[1-3]. Return one of them.