java - 在数组中添加连续的整数对的分而治之算法有问题

Question

因此，我试图了解分而治之原则和单一方法中的多次递归调用。一切正常，但我正在编写的方法的输出有问题。

该方法的目的是返回数组中所有连续数字对的总和。我已经完成了 95%，但没有得到我期望的输出，多年来我一直在用头撞 table 试图找出原因。

数组是:

int[] array = { 11, 6, 87, 32, 15, 5, 9, 21 };

方法是:

public int consecutivePairsSum_DivideAndConquer(int start, int end, int[] array) {
    int leftSum;
    int rightSum;
    int middle = (start + end) / 2;
    if (start == middle) {
        return array[middle];
    } else {
        leftSum = array[start] + array[start + 1];
        leftSum += consecutivePairsSum_DivideAndConquer(start, middle, array);
    }
    if (middle == end) {
        return array[end];
    } else {
        rightSum = array[middle] + array[middle+1];
        rightSum += consecutivePairsSum_DivideAndConquer(middle+1, end, array);
    }
    return leftSum + rightSum;
}

这是我的方法调用:

System.out.println(rF.consecutivePairsSum_DivideAndConquer(0, array.length-1, array));

我认为这一定与我拆分数组的方式有关，但没有多少实验能给我正确的输出。

预期输出:340

实际输出:330

欢迎提出任何建议，这让我抓狂! :p

ps 任何有用的链接到我可以找到关于递归的可靠在线教程/好书的地方也很棒(如果那在 SO 的范围内看看它如何不直接帮助解决编程问题)

Answer 1

算法的概要如下:

基本情况:如果您的数组元素少于两个，则结果为 0 (因为没有对)。

否则:将数组分成两半，计算左右两半的结果，则整个数组的结果为<result of left half> + <result of right half> + <last element of left half> + <first element of right half>。 (因为这里唯一缺少的对是 split 位置的对)。

在java中，它会是这样的:

int consPairSum(int[] array, int left, int right) {
    if(right <= left + 1) return 0;

    int mid = (left + right) / 2;
    int leftPairSum = consPairSum(array, left, mid);
    int rightPairSum = consPairSum(array, mid, right);
    return leftPairSum + rightPairSum + array[mid - 1] + array[mid];
}

应该这样称呼

consPairSum(array, 0, array.length);