Trouver la valeur maximum dans un tableau en utilisant la récursivité

C'est en fait beaucoup plus simple que cela. Le cas de base est que si vous avez atteint la fin du tableau (le 'else' une partie de la ternaire bloc de contrôle ci-dessous). Sinon vous retourner le max du courant et de l'appel récursif.

public static int findMax(int[] a) {
    return findMax(a, 0);
}
private static int findMax(int[] a, int i) {
    return i < a.length
           ? Math.max(a[i], findMax(a, i + 1))
           : Integer.MIN_VALUE;
}

À chaque élément, il est de retour la plus grande de l'élément courant, et de tous les éléments avec un plus grand indice. Integer.MIN_VALUE seront retournés seulement sur des tableaux vides. Cela s'exécute en temps linéaire.

Qu'en est ce une ?

public static int maxElement(int[] a, int index, int max) {
    int largest = max;
    while (index < a.length-1) {
        //If current is the first element then override largest
        if (index == 0) {
            largest = a[0];
        }
        if (largest < a[index+1]) {
            largest = a[index+1];
            System.out.println("New Largest : " + largest); //Just to track the change in largest value
        }
        maxElement(a,index+1,largest);
    }
    return largest;
}

Je suis tombé sur ce fil et il m'a beaucoup aidé. Ci-joint mon code complet à la fois de la récursivité et de diviser&conquer cas.
Le temps d'exécution pour diviser&conquer est légèrement mieux que la récursivité.

//use divide and conquer.
public int findMaxDivideConquer(int[] arr){
    return findMaxDivideConquerHelper(arr, 0, arr.length-1);
}
private int findMaxDivideConquerHelper(int[] arr, int start, int end){
    //base case
    if(end - start  <=  1) return Math.max(arr[start], arr[end]);
    //divide
    int mid = start + ( end - start )/2;
    int leftMax =findMaxDivideConquerHelper(arr, start, mid);
    int rightMax =findMaxDivideConquerHelper(arr, mid+1, end);
    //conquer
    return Math.max( leftMax, rightMax );
}

//use recursion. return the max of the current and recursive call
public int findMaxRec(int[] arr){
    return findMaxRec(arr, 0);
}
private int findMaxRec(int[] arr, int i){
    if (i == arr.length) {
        return Integer.MIN_VALUE;
    }
    return Math.max(arr[i], findMaxRec(arr, i+1));
}

Vous pouvez le faire de manière récursive comme suit.

Récurrentes concernant quelque chose comme cela.

   f(a,n)   = a[n]   if n == size
            = f(a,n+1) if n != size

Mise en œuvre est comme suit.

   private static int getMaxRecursive(int[] arr,int pos) {
         if(pos == (arr.length-1)) {
                return arr[pos];
         } else {           
                return Math.max(arr[pos], getMaxRecursive(arr, pos+1));
         }
   }

et appel ressemblera à ceci

      int maxElement = getMaxRecursive(arr,0);

Solution optimisée

public class Test1 {
    public static int findMax(int[] a, int head, int last) {

        int max = 0, max1 = 0;

        if (head == last) {
            return a[head];

        } else if (a[head] < a[last]) {
            max = findMax(a, head + 1, last);
        } else
            max = findMax(a, head, last - 1);

        if (max >= max1) {
            max1 = max;
        }
        return max1;


    }

    public static void main(String[] args) {
        int arr[] = {1001, 0, 2, 1002, 2500, 3, 1000, 7, 5, 100};
        int i = findMax(arr, 0, 9);
        System.out.println(i);
    }
}

int maximum = getMaxValue ( arr[arr.length - 1 ], arr, arr.length - 1 );

public static int getMaxValue ( int max, int arr[], int index )
{
    if ( index < 0 )
        return max;
    if ( max < arr[index] )
        max = arr[index];
    return getMaxValue ( max, arr, index - 1 ); 
}

J'ai senti que l'utilisation d'un tracker pour la valeur maximale actuelle serait bon.