java - 递归函数来区分数组中的两个值

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;
}

而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 };
}

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