Java 数组中的递归差异

Question

我目前正在学习 Java，但我偶然发现了一个我无法完成的练习。

任务是编写一个递归方法，该方法采用数组和 returns 最大值和最小值的差值。

例如 {12, 5, 3, 8} 应该 return 5 (8 - 3)。重要的是要注意，只允许以正确的顺序比较值 (result = rightValue - leftValue)。例如 12-3 = 9 是不允许的。把它想象成股票价值。你想知道什么时候买卖股票获利最大。

实现此迭代非常容易，但我不知道如何递归执行它。使用分而治之的方法来解决它也是任务的一部分。

Answer 1

算法（这几乎是一个排序任务，然后减法步骤很简单）

1) 首先对数组进行排序（大数组使用递归归并排序，小数组使用递归插入）。

合并排序（https://en.wikipedia.org/wiki/Merge_sort）

插入排序(https://en.wikipedia.org/wiki/Insertion_sort)

2) 使用数组最小索引[0] 得到最小值 & 索引[array.length-1] 得到最大

3)计算差值（不知道你所说的正确顺序是什么意思？）

Answer 2

我在这里使用了分而治之的方法。我相信这里的技巧是将 middle 包含在我们将主数组拆分成的两个数组中。

/* 此处忽略边缘情况 */

int findMax(int[] arr, int left, int right){

if(right-left == 1) return (arr[right]-arr[left]);

int middle = left + (right-left)/2;

int max1 = findMax(arr, left, middle);
int max2 = findMax(arr, middle, right);

if(max1 >= 0 && max2 >= 0) return max1+max2;

else return Math.max(max1,max2);

}

Answer 3

嗯，我认为递归在这方面不是很有效。你可能永远不会这样做（除了家庭作业）。像这样的事情就可以做到：

int findGreatestDifference(Vector<Integer> numbers, int greaterDifference){
    if(numbers.size() == 1 ) //return at last element
        return greaterDifference;
    int newDifference = (numbers.get(0) - numbers.get(1));
    if (newDifference > greaterDifference)
        greaterDifference = newDifference;

    numbers.remove(numbers.size() - 1);
    findGreatestDifference(numbers, greaterDifference);
    return greaterDifference;
}

第一次调用它时，传递 0 作为较大的差异，我再次发现这不是一种有效的方法。迭代会更好。

希望对您有所帮助。

Java 数组中的递归差异

Java recursive difference in array

java

arrays

iteration

recursion

divide-and-conquer