递归函数在阵列

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]因为THI s的线路retArr[1] = retArr[1] + 1;

这是因为我不知道在哪里保存索引，所以，我怎么可以保存索引？

*我不知道getMax(int [] arr, int []retArr) 它的第二PARAM可以是不同的，也许

我不能添加其他参数，也许改变的getMax(int [] arr, int []retArr)第二PARAM，我不能用静态变量

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应该是传递给函数的附加参数。 （和当前索引其他参考相应更新）

UPDATE：

我认为，这里的关键是要了解“分而治之”，在那里你分手的问题分解成更小的问题，然后进行排序，通过对最好的。像这样的东西（如果多一点别扭那么正常情况下）

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

递归函数的每次调用（或堆栈）是它自己的上下文。这意味着在其中声明的变量在递归调用中不会被覆盖。这个想法是，你递归地解决了一个难题，直到你无法进一步细分。然后，您将每次通话的结果放在一起，直到您获得最终答案为止。 （这与没有价值的情况下，像斐波那契序列效果更好），另外请注意，任何可以在一个循环做总是会更有效率，然后递归。