Brauchen Sie einige einfache Logikhilfe, für ein paar Stunden stecken geblieben

Question

Das Problem ist, eine beliebige Anzahl von Zahlen zu nehmen, und finden Sie die höchstmögliche Summe der Differenz (mit absoluter Wert) zwischen aufeinanderfolgenden Zahlen. Zum Beispiel würden die Nummern 1 2 und 3 3 1 2 angeordnet werden, um eine Summe von 3 zu erhalten (3-1 = 2 und 1-2 = 1).

Jetzt waren meine ersten Gedanken, die höchste Zahl in der Liste zu nehmen, gefolgt von der niedrigsten Nummer und arrangieren auf diese Weise bis zum Ende, aber das funktioniert nicht, da das Ende der Liste am Ende alle Zahlen haben wird in der Mitte häufen sich fast keine Unterschiede an. Die einzige andere Sache, an die ich gedacht habe, ist, jede einzelne mögliche Reihenfolge zu finden und die höchste Summe zurückzugeben, aber mit einer längeren Liste wird das viel zu lange dauern und ich nehme an, dass es einen besseren Weg geben könnte.

Als Referenz sind hier einige Beispiele Eingangs- und Ausgangsnummern

9 2 5 3 1 -> 21 
7 3 4 5 5 7 6 8 5 4 -> 24 

überhaupt Hilfe wäre sehr willkommen, auch wenn sie in der richtigen Richtung mit mir gerade.

Answer 1

Es gibt zwei Ansätze für dieses Problem.

Ansatz 1:

Brute-Force.

Ansatz 2:

Auszufinden ein Algorithmus, wie die Zahlen zu arrangieren.

Ich mag Ansatz 2 immer besser, wenn es machbar ist.

Es scheint vernünftig, dass Sie eine hohe Summe erhalten würde, wenn man die Zahlen hoch-tief-hoch-tief-hoch ...

durch Sortieren der Zahlen

So starten bestellen und sie dann in zwei gleich große Gruppen unterteilen von niedrigen und hohen Zahlen. Wenn es eine ungerade Anzahl von Zahlen gibt, bleibt die mittlere Zahl übrig.

Dann wählen Sie einfach Zahlen abwechselnd aus den beiden Gruppen.

Es ist leicht zu beweisen, dass die Reihenfolge der inneren Zahlen keine Rolle spielt, solange Sie bei der Reihenfolge "hoch-niedrig-hoch-niedrig" bleiben. Da jedoch die Anfangs- und Endnummer nur einen Nachbarn hat, sollten die erste und die letzte Nummer die mittleren Zahlen sein.

Schließlich, wenn Sie eine ungerade Anzahl von Zahlen haben, legen Sie die letzte Zahl am Anfang oder Ende, was auch immer den größten Unterschied ergibt.

Beispiel:

7 3 4 5 5 7 6 8 5 4 -> [sort] -> 3 4 4 5 5 5 6 7 7 8 
high numbers: 5 6 7 7 8 
low numbers: 3 4 4 5 5 

Arranged: 
5 3 6 4 7 4 7 5 8 5 = 24 

Beispiel:

9 2 5 3 1 -> [sort] -> 1 2 3 5 9 
high numbers: 5 9 
low numbers: 1 2 
left over: 3 

Arranged: 
3 5 1 9 2 = 21  (3 goes at the start, because |3-5| > |3-2|)