c++ - 整数数组求和的分治算法

Question

我在分而治之算法方面遇到了一些麻烦，正在寻求帮助。我正在尝试编写一个名为 sumArray 的函数来计算整数数组的总和。

这个函数必须通过将数组分成两半并对每一半执行递归调用来完成。我曾尝试使用与我在编写递归求和算法和分而治之算法来识别数组中的最大元素时使用的概念类似的概念，但我正在努力将这两种想法结合起来。

下面是我为 sumArray 编写的代码，它可以编译，但没有返回正确的结果。

int sumArray(int anArray[], int size)
{
    int total = 0;
    //base case
    if (size == 0)
    {
        return 0;
    }
    else if (size == 1)
    {
        return anArray[0];
    }

    //divide and conquer
    int mid = size / 2;
    int lsum = anArray [mid] + sumArray(anArray, --mid);
    int rsize = size - mid;
    int rsum = anArray[size - mid] + sumArray(anArray + mid, --rsize);
    return lsum + rsum;
}

我发现问题在于该函数在计算 rsum 时包含了 lsum 的值。我知道问题在于我使用 rsize(一个等于原始数组大小减去中点的变量)对 sumArray 的递归调用。但是，出于某种原因，我似乎无法确定修复方法。

我觉得问这个问题很傻，因为我知道答案就在眼前，但我该如何修复我的函数以使其返回准确的结果？

更新:感谢所有有用的回复，我已经修复了我的代码，因此它可以很好地编译和运行。我会在这里留下我的原始代码，以防其他人正在努力分而治之，并且可能会犯类似的错误。有关正确解决问题的功能，请参阅@Laura M 的回答。 @haris 的回复也很好地解释了我的代码在哪里出错。

Answer 1

int sumArray(int anArray[], int size)
{
    //base case
    if (size == 0)
    {
        return 0;
    }
    else if (size == 1)
    {
        return anArray[0];
    }

    //divide and conquer
    int mid = size / 2;
    int rsize = size - mid;
    int lsum = sumArray(anArray, mid);
    int rsum = sumArray(anArray + mid, rsize);
    return lsum + rsum;
}