配列内の2つの値の差異への再帰関数

Question

私はJavaを使用しています。

私は2つの値の差を計算し、サイズ2の配列を返す再帰関数を実装する必要があります[MAXIMUM_DIFF, STARTINDEX]。以下のアレイについて

：最大差が70 (60-(-10)=70)であり、60のインデックスIから90％を有する2

あるため[70,2]：

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

再帰的な方法は、サイズ2の配列を返します解決策：

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

} 

しかし、結果は、Th1ため[70,7]の代わり[70,2]です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 }; 
} 

再帰関数の各呼び出し（またはスタック）は、独自のコンテキストです。つまり、それで宣言された変数は再帰呼び出しで上書きされません。アイデアは、あなたがそれをさらに分解することができなくなるまで、難しい問題を再帰的に打破することです。次に、あなたはあなたが最終的な答えを得るまで、各呼び出しの結果を1つずつまとめて解決します。 （これはフィボナッチシーケンスのような単純なケースではうまくいきます）ループ内で実行できるものは、常により効率的で再帰的であることにも注意してください。