Поиск максимального числа с Divide и Conquer в Java

Question

Я пытаюсь найти максимальное число в массиве с помощью метода Divide и Conquer (рекурсия). Но когда я компилирую этот код, я получаю исключение ArrayIndexOutOfBounds.

Я не уверен, где я ошибаюсь. Вот мой фрагмент кода:

public class ... { 
    int[] A = {2,4,5,1,6,7,9,3}; 
    int max; 

    public void solution() { 
    max = findMax(0, A.length-1); 
    //print max 
    } 

    private int findMax(int a, int b){  
    if(b-a == 1){ 
     return A[a]>A[b] ? A[a] : A[b]; 
    } 
    else if(a==b){ 
     return A[a]; 
    } 

    return findMax(findMax(a, (a+b)/2), findMax((a+b)/2 +1, b)); 
    } 

} 

Answer 1

Проблема заключается в последней строке:

return findMax(findMax(a, (a+b)/2), findMax((a+b)/2 +1, b)); 

Это позволит использовать результаты ваших findMax() методов в качестве аргументов для другого findMax() вызова, который означает, что они будут использоваться в качестве индексов в массиве. Это даст вам неправильный результат или вызовет ArrayIndexOutOfBoundsException.

То, что вы хотите сделать, это вернуть максимум двух findMax() вызовов:

return Math.max(findMax(a, (a+b)/2), findMax((a+b)/2 + 1, b)); 

Answer 2

Я не думаю, что это лучшее использование рекурсии. Тем не менее, мне было бы легче следовать. Надеюсь, это поможет, ура!

public static int maxI(int[] x, i index){ 
    if (index > 0) 
    { 
    return Math.max(x[i], maxI(x, i-1)) 
    } 
    else 
    { 
    return x[0]; 
    } 
}