为了更好地理解递归，我尝试在我的代码中打印一些输出，以便我可以研究这些步骤。
#include <tuple>
#include <string>
#include <iostream>
#include <map>
#include "print.h"
std::tuple<int, int, int> find_max_crossing_subarray(int A[], int low, int mid, int high)
{
int max_left, max_right;
int left_sum = std::numeric_limits<int>::min();
int sum = 0;
for(int i = mid; i >= low; i--) {
sum += A[i];
if(sum > left_sum) {
left_sum = sum;
max_left = i;
}
}
int right_sum = std::numeric_limits<int>::min();
sum = 0;
for(int j = mid + 1; j <= high; j++) {
sum += A[j];
if(sum > right_sum) {
right_sum = sum;
max_right = j;
}
}
return std::make_tuple(max_left, max_right, left_sum + right_sum);
}
std::tuple<int, int, int> find_max_subarray(int A[], int low, int high)
{
if(high == low) {
return std::make_tuple(low, high, A[low]);
}
else {
int mid = (high + low) / 2;
std::tuple<int, int, int> left(find_max_subarray(A, low, mid));
std::cout << "left: ";
print(left);
int left_low, left_high, left_sum;
std::tie(left_low, left_high, left_sum) = left;
std::tuple<int, int, int> right(find_max_subarray(A, mid + 1, high));
std::cout << "right: ";
print(right);
int right_low, right_high, right_sum;
std::tie(right_low, right_high, right_sum) = right;
std::tuple<int, int, int> cross(find_max_crossing_subarray(A, low, mid, high));
std::cout << "cross: ";
print(cross);
int cross_low, cross_high, cross_sum;
std::tie(cross_low, cross_high, cross_sum) = cross;
if(left_sum >= right_sum && left_sum >= cross_sum) {
return left;
}
else if(right_sum >= left_sum && right_sum >= cross_sum) {
return right;
}
else {
return cross;
}
}
}
int main()
{
int arr_3[3] = {-3, 2, 3};
int arr_4[4] = {5, -23, 1, 44};
int arr_6[6] = {5, -23, 1, 44, -2, 5};
int arr[16] = {-23, 3, 9 ,7, -12, 87, -25, 2, 3, 5, 32, -8, 6, -82, 3, 9};
print(arr_4, 4);
std::tuple<int, int, int> maple(find_max_subarray(arr_4, 0, 3));
print(maple);
return 0;
}
输出：：
5 -23 1 44
left: 0 0 5
right: 1 1 -23
cross: 0 1 -18
left: 0 0 5
left: 2 2 1
right: 3 3 44
cross: 2 3 45
right: 2 3 45
cross: 0 3 27
2 3 45
我理解输出的前三行（即左、右、十字开始的位置）。但我不明白第四行及以上来自哪里。我尝试追溯这些函数，我一直在想我应该left: 1 1 -23在cross: 0 1 -18.
编辑：
我应该指出left: 2 2 1，虽然很难想象，但我还是有点理解的。递归已经结束，代码只是向后级联。
第二次编辑：
我猜第四行发生的事情是第一行find_max_subarray正在完成，它正在返回if函数代码中的第一条语句。现在它正在移动到第二个find_max_subarray。
第三次编辑：
我想我的困惑是代码不会向后级联，而是在到达递归结束后返回到第一个调用。
第四次编辑：
当我出去玩六个元素时，它似乎并没有简单地回到第一个电话。
5 -23 1 44 -2 5
left: 0 0 5
right: 1 1 -23
cross: 0 1 -18
left: 0 0 5
right: 2 2 1
cross: 0 2 -17
left: 0 0 5
left: 3 3 44
right: 4 4 -2
cross: 3 4 42
left: 3 3 44
right: 5 5 5
cross: 3 5 47
right: 3 5 47
cross: 2 5 48
2 5 48
我的意思是我猜这是因为子数组有三个元素而不是两个。所以有两对而不是一对。当您认为它是理所当然但无法从视觉上看到它时，这是有道理的。
最后编辑：
所以当我出去到8点时，它是成对的。前两个元素，然后返回原始调用。接下来的两对并返回调用。我不完全确定为什么在奇怪的情况下它不会在第一对和第二对以及第一对和第三对都完成之前返回调用。
5 -23 1 44 -2 5 6 -3
left: 0 0 5
right: 1 1 -23
cross: 0 1 -18
left: 0 0 5
left: 2 2 1
right: 3 3 44
cross: 2 3 45
right: 2 3 45
cross: 0 3 27
left: 2 3 45
left: 4 4 -2
right: 5 5 5
cross: 4 5 3
left: 5 5 5
left: 6 6 6
right: 7 7 -3
cross: 6 7 3
right: 6 6 6
cross: 5 6 11
right: 5 6 11
cross: 2 6 54
2 6 54
问题解决了：
我在理解递归时遇到的问题是，对于每个递归步骤，我都使用原始high值。实际上，我使用正确的块将它写在纸上，high并且所有内容都融合在一起。