了解递归/如何组合子问题（最大子阵列算法）

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。然后返回（低，高，A [低]），在这种情况下将是（1,1，A [1]）。现在我不明白在调用的其余部分中如何处理这些值。

此外，我不明白该算法实际上如何比较长度> 1的子阵列。任何人都可以向我解释一旦该函数的一个调用已经触底，该算法如何继续，请？

Answer 1

简而言之： 让A成为n长度的数组。你想要计算你称之为A的Find-Maximum-Subarray(A, 0, n-1) sou的最大子阵列。现在尝试使问题更容易：

1. 案件。高=低： 在这种情况下，Array只有1个Element，因此解决方案很简单
2. 高！=低 在这种情况下，难以找到解决方案。所以尽量减少问题。如果我们将数组A切割成半长的数组B1和B2会发生什么。现在只有3个新病例 a）A的Max子阵列也是B1的子阵列但不是B2的子阵列 b）A的最大子阵列也是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.