java - 整数数组的除法和

Question

我编写了以下程序，使用 Java 中的分治递归算法求所有整数的总和:

但不知何故，总和不正确。

public class DivideAndConquerSum {
 public static void main(String[] args) {
    int[] arr = new int[]{2, 3, 4, 5};
    System.out.println(calculateRecursiveSum(arr, 0, arr.length));
  }
  static long sum = 0;
  static long calculateRecursiveSum(int[] arr, int low, int high) {
    if (high == low) {
      return arr[0];
    } else {
      int mid = (high + low) / 2;
      sum = calculateRecursiveSum(arr, low, mid) +
            calculateRecursiveSum(arr, mid + 1, high);
    }
    return sum;
  }
}

任何人都可以让我知道代码中有什么问题来解决它吗？在这种情况下仅假设正整数。

Answer 1

您的方法基本上会重新计算 mid，因此您需要返回该点的值。它更适合二分查找。但进行以下更改，它就会起作用。

       static long calculateRecursiveSum(int[] arr, int low, int high) {
          if (high == low) {
                return 0;
            }
            int mid = (high + low) / 2;
            return arr[mid] + calculateRecursiveSum(arr, low, mid) + 
                      calculateRecursiveSum(arr, mid+1, high);
       }