Java recursive difference in array

Question

J'apprends actuellement Java et je suis tombé sur un exercice que je ne peux pas terminer.

La tâche consiste à écrire une méthode récursive qui prend un tableau et renvoie la différence entre la plus grande et la plus petite valeur. Par exemple, {12, 5, 3, 8} doit renvoyer 5 (8 - 3). Il est important de noter qu'il est seulement permis de comparer les valeurs dans le bon ordre (result = rightValue - leftValue). Par exemple 12-3 = 9 ne serait pas autorisé. Pensez-y comme des valeurs boursières. Vous voulez savoir à quelle heure acheter et vendre les actions pour faire le plus gros bénéfice.

Il était facile d'implémenter ce itératif mais je n'ai aucune idée de comment le faire récursif. Aussi, il est de la tâche de le résoudre en utilisant diviser pour régner.

Answer 1

Je l'ai utilisé diviser pour mieux régner approche ici. Je crois que l'astuce ici est d'inclure le milieu dans les deux tableaux dans lesquels nous divisons le tableau principal.

/* cas de pointe ici * ignorés/

int findMax(int[] arr, int left, int right){ 

if(right-left == 1) return (arr[right]-arr[left]); 

int middle = left + (right-left)/2; 

int max1 = findMax(arr, left, middle); 
int max2 = findMax(arr, middle, right); 

if(max1 >= 0 && max2 >= 0) return max1+max2; 

else return Math.max(max1,max2); 

} 

Answer 2

algorithme (ce qui est à peu près une tâche de tri, puis l'étape de soustraction est trivial)

1) Trier d'abord les tableaux (utilisez sorte de fusion récursive pour les grands tableaux et insertion récursive pour les tableaux plus petits).

tri fusion (https://en.wikipedia.org/wiki/Merge_sort)

type d'insertion (https://en.wikipedia.org/wiki/Insertion_sort)

2) Utilisez les tableaux le plus petit index [0] pour obtenir l'indice de valeur & plus petit [array.length-1] pour obtenir le plus grand

3) calculer la différence (ne sais pas ce que vous entendez par ordre?)

Answer 3

Eh bien, je ne pense pas que la récursivité est très efficace sur ce point. Vous ne feriez probablement jamais cela (autre que les devoirs). Quelque chose comme ça le ferait:

int findGreatestDifference(Vector<Integer> numbers, int greaterDifference){ 
    if(numbers.size() == 1) //return at last element 
     return greaterDifference; 
    int newDifference = (numbers.get(0) - numbers.get(1)); 
    if (newDifference > greaterDifference) 
     greaterDifference = newDifference; 

    numbers.remove(numbers.size() - 1); 
    findGreatestDifference(numbers, greaterDifference); 
    return greaterDifference; 
} 

première fois que vous appelez, passer 0 comme une plus grande différence, et encore je ne trouve pas cela comme un moyen efficace de le faire. L'itération serait bien meilleure pour cela.

J'espère que cela aide.