遞歸函數在陣列

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

遞歸函數的每次調用（或堆棧）是它自己的上下文。這意味着在其中聲明的變量在遞歸調用中不會被覆蓋。這個想法是，你遞歸地解決了一個難題，直到你無法進一步細分。然後，您將每次通話的結果放在一起，直到您獲得最終答案爲止。 （這與沒有價值的情況下，像斐波那契序列效果更好），另外請注意，任何可以在一個循環做總是會更有效率，然後遞歸。