数组中两个值之差的递归函数

Question

我在用Java。

我需要实现一个递归函数，计算每两个值之间的差值，并返回大小为2的数组[MAXIMUM_DIFF，STARTINDEX]。

对于以下阵列：

arr = {1, 4, 60, -10, 2, 7, 56, -10}

递归方法返回大小为2的数组：[70,2]，因为最大差值为70（60-（-10）=70），60的索引为2。

我有90%来自解决方案：

public static int[] getMax(int[] arr) {

    int [] retArr = new int[2];

    if(arr.length == 1)
        return retArr;
    else {
        return getMax(arr, retArr);
    }

}

public static int[] getMax(int[] arr, int[] retArr) {
    if(retArr[1] == arr.length - 1)
        return retArr;

    int currentMaxVal = arr[retArr[1]] - arr[retArr[1] + 1];

    if(currentMaxVal > retArr[0]) {
        retArr[0] = currentMaxVal;
    }

    retArr[1] = retArr[1] + 1;

    return getMax(arr, retArr);

}

但是结果是[70,7]而不是[70,2]，因为这行retArr[1]=retArr[1]1

这是因为我不知道在哪里保存索引，所以如何保存索引？

*我不确定第二个参数的getMax（int[]arr， int[]retArr）它可以是不同的也许

我不能添加其他参数，可能是为了更改getMax（int[]arr，int[]retArr）的第二个参数，我不能使用静态变量




Answer 1

if(currentMaxVal > retArr[0])
{
  retArr[0] = currentMaxVal;
}

retArr[1] = retArr[1] + 1;

应该是

if(currentMaxVal > retArr[0])
{
  retArr[0] = currentMaxVal;
  retArr[1] = currentIndex;
}

并且当前索引应该是传递给函数的附加参数。（

更新：

我认为这里的重点是理解“分而治之”，即把问题分解成一个较小的问题，然后再进行排序，找出最好的问题。类似的情况（如果比正常情况更尴尬）

public static int[] getMax(int[] arr, int[] retArr) {
    // Return case
    if (retArr[1] >= arr.length - 1)
        return new int[] { Integer.MIN_VALUE, retArr[1] };

    // Save context
    int index = retArr[1];
    int value = arr[index] - arr[index + 1];

    // Call recursion
    retArr[1]++;
    int[] temp = getMax(arr, retArr);

    // Return best between current case and recursive case
    if (temp[0] > value)
        return temp;
    else
        return new int[] { value, index };
}

递归函数的每个调用（或堆栈）都是它自己的上下文。这意味着其中声明的变量不会在递归调用中被覆盖。这个想法是，你递归地分解一个难题，直到你不能再分解它。然后你把每个电话的结果一次一个地放在一起解决，直到你有最终的答案。（这在像斐波那契序列这样不那么琐碎的情况下效果更好）还要注意，任何可以在循环中完成的事情总是比递归更有效。