分割して征服する配列の最大値

Question

これは宿題であることを前提としています。なぜ私は「宿題」というタグを使用できないのか分かりません。

"int maximum（int [] a、int l、int r）"を書く必要があります。これは、分割と征服のアプローチを使用して 'l'から 'r'に及ぶ配列Aの最大値を見つけます。 ベースケースは、Aの内部に単一の要素がある場合になります。したがって、A.length == 1の場合、要素を返します。再帰的な部分は、A [1]からA [mid]まで、そしてA [mid + 1]からA [r]にまたがる2つの部分配列で配列を分割しなければならない。理論的には、私はそれで大丈夫ですが、私はStackOverflowErrorを取得し続けて、なぜ私は理解していません。

public class Maximum { 
public static void main(String[] args) { 
    int[] A = {0, 5, 281, 3, 9, 4, 88, 16, 17, 60}; 
    int l = 0; 
    int r = A.length-1; 
    System.out.println("Maximum of the array: "+maxArray(A, l, r)); 
} 
public static int maxArray(int[] A, int l, int r) { 

    //Assuming that the index of array is '0' and not '1', l is 0. Else, put 1. 

    if (A.length == 1) { 
     return A[l]; 
    } 

    int mid = r/2; 
    int maxLeft = 0; 
    int maxRight = 0; 

    maxLeft = maxArray(A, l, mid);  //Here is the StackOverflowError! 
    maxRight = maxArray(A, mid+1, r); 

    if (maxLeft < maxRight) { 
     return maxRight; 
    } else 
return maxLeft; 
} 
} 

Answer 1

midの計算に問題があります。それは、その横に

int mid = (l+r)/2; 

でなければなりません

あなたは常にあなたの方法に元の配列を渡しているので、A.lengthしかすることができるので、

if (A.length == 1) { 
    return A[l]; 
} 

は

if (l == r) { 
    return A[l]; 
} 

する必要があります元の配列に単一の要素がある場合は1です。左側の要素のインデックスは、右要素のインデックスと同じである場合、それは配列を意味分割統治アプローチにおいて

Answer 2

我々は中間要素のインデックスを算出する際に、その平均がまた2

によって最初と最後のインデックス分割の和であり、 1つの要素しか持たず、その単一の配列要素だけを返します。

あなたのソリューションは、次のとおりです。

public class Helloworld{ 

public static void main(String []args){ 
    int[] A = {0, 5, 281, 3, 9, 4, 88, 16, 17, 60}; 
int l = 0; 
int r = A.length-1; 
System.out.println("Maximum of the array: "+maxArray(A, l, r)); 
} 

public static int maxArray(int[] A, int l, int r) { 

//Assuming that the index of array is '0' and not '1', l is 0. Else, put 1. 

if (l == r) { // checking codition/ 
    return A[l]; 
} 

int mid = (l+r)/2; // Calculating mid. 
int maxLeft = 0; 
int maxRight = 0; 

maxLeft = maxArray(A, l, mid);   
maxRight = maxArray(A, mid+1, r); 

if (maxLeft < maxRight) { 
    return maxRight; 
} else return maxLeft; 
}}