整数数组和的分治算法

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;
}

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;
}