Возникли проблемы с алгоритмом «разделяй и властвуй» для добавления последовательных пар целых чисел в массив

Question

Итак, я пытаюсь разобраться с принципом «разделяй и властвуй» и множественными рекурсивными вызовами в одном методе. Все идет хорошо, но у меня проблема с выводом метода, который я пишу.

Цель метода - вернуть сумму всех пар последовательных чисел в массиве. Я на 95%, но не получаю ожидаемого результата и целую вечность бью себя по столу, пытаясь понять, почему.

Массив:

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

Любые предложения приветствуются, это сводит меня с ума! : Р

ps Любые полезные ссылки на то, где я могу найти солидный онлайн-учебник / хорошую книгу о рекурсии, также были бы хороши (если это входит в сферу компетенции SO, понимая, что это не является прямой помощью при программировании)

Answer 1

кто сказал, что разделяй и властвуй нужно разделить на равные части, которые тебе просто нужно разделить на похожие на себя проблемы. почти 1 лайнер.

static private int doTheThing(int[] list){
    if (list.length==2)
        return list[0]+list[1];
    return list[0]+list[1]+doTheThing(Arrays.copyOfRange(list,1,list.length));
}

Answer 2

Вот схема алгоритма:

Базовый случай: если в вашем массиве менее двух элементов, результатом будет 0 (поскольку пар нет).

В противном случае: разделите массив на две половины, вычислите результаты для левой и правой половин, тогда результат для всего массива будет <result of left half> + <result of right half> + <last element of left half> + <first element of right half> (потому что единственная пара, отсутствующая здесь, это пара в месте разделения) .

В 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);