Java rekursive Unterschied in Array

Question

Ich lerne derzeit Java und ich stolperte über eine Übung, die ich nicht beenden kann.

Die Aufgabe besteht darin, eine rekursive Methode zu schreiben, die ein Array akzeptiert und die Differenz zwischen dem größten und dem kleinsten Wert zurückgibt.

Zum Beispiel {12, 5, 3, 8} sollte 5 (8 - 3) zurückgeben. Es ist wichtig zu beachten, dass nur Werte in der richtigen Reihenfolge verglichen werden dürfen (result = rightValue - leftValue). Zum Beispiel wäre 12-3 = 9 nicht erlaubt. Denken Sie daran wie Aktienwerte. Sie möchten herausfinden, wann Sie die Aktien kaufen und verkaufen, um den größten Gewinn zu erzielen.

Es war leise einfach, dieses iterative zu implementieren, aber ich habe keine Ahnung, wie man es rekursiv macht. Auch es ist Teil der Aufgabe, es zu lösen, indem man Teile und herrsche.

Answer 1

ich teile verwendet habe und herrsche hier Ansatz. Ich glaube, der Trick besteht hier darin, die Mitte in beide Arrays aufzunehmen, in die wir das Haupt-Array aufteilen.

/* Grenzfälle hier */

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

Algorithm (dies ziemlich viel eine Art Aufgabe, dann wird der Subtraktionsschritt trivial ist)

1) zuerst sortieren die Arrays (merge verwenden rekursive Sortier für große Arrays und rekursive Einfügung für kleinere Arrays). Verwenden Sie

Merge sort (https://en.wikipedia.org/wiki/Merge_sort)

Insertion sort (https://en.wikipedia.org/wiki/Insertion_sort)

2) die Arrays kleinsten Index [0] erhalten der kleinste Wert & Index [array.length-1] die größte zu bekommen

3) berechnen den Unterschied (weiß nicht, was Sie mit dem richtigen Reihenfolge das?)

Answer 3

Nun, ich glaube nicht an diese Rekursion ist sehr effektiv ignoriert. Das würdest du wahrscheinlich nie tun (außer Hausaufgaben). So etwas wie dies würde es tun:

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

erstes Mal, wenn Sie es nennen, passiert 0 als größere Differenz, und wieder ich dies nicht als einen effektiven Weg finden, es zu tun. Iteration wäre dafür viel besser.

Ich hoffe, das hilft.