Ein Problem ist nur, dass wir ja bereits $2(k-1)$ Zugriffe auf $A$ brauchen, um $B$ überhaupt erst berechnen zu können. Die entscheidende Einsicht ist hier, dass wir $B$ nicht explizit berechnen müssen: nein, erst wenn der Algorithmus den Wert $B[i]$ abfragt, schlagen wir $A[i]$ und $A[i+1]]$ nach und geben $A[i]-A[i+1]$ zurück. Pro $B$-Zugriff benötigen wir also zwei $A$-Zugriffe. $◻$

Stellen Sie sich vor, Sie beobachten ein das oben beschriebene Spiel zwischen Alice und Eve und pausieren zu einem bestimmten Zeitpunkt. Alice hat also bestimmte Indizes in $\{1,\dots ,n\}$ angefragt und Eve hat geantwortet (es wird nun vorteilhaft sein, die Array-Indizes von $1$ bis $n$ laufen zu lassen).

Stellen Sie die richtigen Fragen. In diesem Falle: Egal ob Alice und Eve im bisherigen Verlauf optimal gespielt haben oder nicht, wieviele weitere Zugriffe benötigt Alice, wenn ab jetzt beide optimal spielen?

Sehen Sie insbesondere, dass die gerade gestellte Frage komplexer ist als die, wieviele Zugriffe Alice bei einem Array der Länge $n$ braucht; sie ist komplexer, weil die Antwort eben nicht nur von $n$ abhängt, sondern auch vom bisherigen Spielverlauf. Paradoxerweise werden Fragen oft einfacher zu beantworten, wenn man sie (auf die richtige Weise) verallgemeinert und dadurch scheinbar komplexer macht.

Welche Information brauchen Sie? Zur Beantwortung der oben gestellten Frage brauchen wir als Information die Länge $n$ des Arrays und den bisherigen Spielverlauf. Also zum Beispiel

Warten Sie! Enthält obiges Bild wirklich die gesamte Information, um den Spielverlauf zu rekonstruieren? Nein! Hierfür bräuchten wir die zeitliche Abfolge der Anfragen. Eine vollständige Beschreibung des Spielverlaufs wäre also eine Folge von Indizes $$i_1,i_2,\dots ,i_k\in \{1,\dots ,n\},$$ welche die von Alice gestellten Anfragen darstellt, zusammen mit einer Reihe von reellen Zahlen $$r_1,r_2,\dots ,r_k\in \mathbb{R},$$ welche Eves Antworten darstellen, sodass $A[i_1]=r_1,\dots ,A[i_k]=r_k$ und die Folge $r_1,\dots ,r_k$ selbst unimodal ist.

Das obige Bild stellt dies fast dar, allerdings nur fast, da es die Reihenfolge ignoriert. Müssen wir aber die Reihenfolge überhaupt kennen, um die Frage zu beantworten: Wieviele weitere Zugriffe benötigt Alice, wenn ab jetzt beide optimal spielen? Für die Beantwortung dieser Frage ist die Reihenfolge, in welcher Alice die in der Vergangenheit liegenden Zugriffe getätigt hat, irrelevant. Vergleichen Sie es mit einem Schachspiel:

Um zu entscheiden, welcher Zug für Weiß nun optimal ist, ist es irrelevant, wie Tarrasch und Euwe zu dieser Position gelangt sind. Wichtig ist einzig und allein die Position. Daher: ja, das obige Bild mit den roten Balken ist ausreichend, um unsere Frage zu beantworten.

Es ist sogar zuviel Information. Ich behaupte, wichtig sind allein die im unteren Bild stark roten Balken; die blassen können wir ignorieren:

In der Tat: das Maximum liegt sicherlich innerhalb der drei stark roten Balken. Eine optimal spielende Alice wird von nun an nie mehr außerhalb dieses Bereichs auf das Array zugreifen. Wir können also die blass roten Balken vergessen und uns nur die Position und Höhe der stark roten merken:

Im nächsten Schritt wird Alice einen Index zwiscehn $$ und $$ anfragen und die Antwort mit $$ vergleichen. Alice muss sich also nicht nur die Positionen $$ merken, sondern auch die Werte des Arrays an diesen Positionen. Für die Beantwortung der Frage Wieviele weitere Zugriffe benötigt Alice? spielen die genauen Werte allerdings keine Rolle! Für einen optimalen Spielverlauf ist nur die Ordnung der Werte entscheidend (also welche größer und welche kleiner sind als andere); da Eve mit reellen Zahlen spielt, kann sie sicherlich immer eine weitere Zahl zwischen zwei gegebenen finden. Wir stellen also fest: um den optimalen weiteren Spielverlauf zu bestimmen, sind die genauen Werte irrelevant; wir müssen nur kennen $$ und natürlich wissen, dass $$ gilt. Ja nicht einmal $$ müssen wir uns merken. Kenntnis der natürlichen Zahlen $$ und $$ reicht völlig aus, um die optimale Anzahl weiterer Zugriffe zu bestimmen.

Reduzieren Sie Information! Die Antwort auf die Frage Wieviele weitere Zugriffe benötgit Alice, wenn von nun an beide optimal spielen? hängt nur von den Zahlen $$ und $$ ab.

Führen Sie neue Notation ein! Definieren wir $$ als die Anzahl von weiteren Zugriffen, die Alice benötigt, um das Maximum der unimodalen Funktion zu bestimmen, wenn beide optimal spielen und $$ gilt. Wie oben argumentiert, hängt das nicht von $$ ab, wir können also $$ statt $$ schreiben.

Erinnern wir uns an die ursprüngliche Frage: wieviele Zugriffe brauchen wir, um das Maximum eines unimodalen Arrays $$ zu finden? In diesem Szenario gibt es kein $$ und kein $$, da Alice noch gar keine Fragen gestellt hat. Sei also $$ der erste Index, den Alice anfragt. Da per Konvention $$ gilt, haben wir $$ und können nun $$ setzen und wissen, dass Alice von nun an (wenn beide optimal spielen) weitere $$ Zugriffe benötigt. Um die Gesamtzahl zu minimieren, muss Alice den Parameter $$ optimieren und benötigt daher insgesamt $$ Zugriffe. Das $$ beszieht sich auf den ersten Zugriff, den auf den Index $$. Wenden wir uns nun wieder unserer Funktion $$ zu und versuchen, sie zu verstehen.

Sammeln Sie einfache Fakten. Was wissen wir über $$?

1. Nun, zum Beispiel $$. Klar: wenn $$ und $$, dann liegt das Maximum des Arrays beim Index $$; keine weiteren Fragen nötig.
2. Links-Rechts-Symmetrie: $$. Die Komplexität ändert sich nicht, wenn wir Array und angefragte Indizes einfach von rechts nach links umkehren.
3. Monotonie: $$. Klar: größere Intervalle können es für Alice nicht einfacher machen.

Spielen Sie selbst! Lassen Sie uns kurz in die Rollen von Alice und Eve schlüpfen. Angenommen, Alice fragt einen Index $$ an mit $$:

Eves Antworten fallen in zwei Kategorien. Entweder ist $$ oder $$. Wie soll Eve nun antworten?

• Falls $$ gilt, dann können wir von nun an $$ vergessen und mit den drei Indizes $$ weiterspielen. Alice benötigt also noch $$ weitere Zugriffe.
• Fals $$ gilt, dann können wir $$ vergessen und mit den Indizes $$ weiterspielen. Alice benötigt also noch $$ weitere Zugriffe.

In Worten: Alice hat zwei Intervalle mit Längen $$. Durch den Zugriff auf $$ zerlegt Alice das erste Intervall und erhält somit drei Intervalle mit Lägen $$. Eve kann sich nun entscheiden, ob das Spiel auf den ersten beiden Intervallen fortgesetzt wird, also $$ oder auf den letzten beiden, also $$. Welche Entscheidung optimal ist, hängt nur davon ab, ob $$ oder $$ größer ist. Ein Spielzug lässt sich nun also wie folgt darstellen: Gegeben ein Paar $$, zum Beispiel $$, zerlegt Alice die erste Zahl und erhält ein Tripel, zum Beispiel: $$. Eve kann sich nun für das erste Paar $$ oder das zweite Paar $$ entscheiden und nimmt natürlich das "größere", hier also $$. Als Tabelle:

Es sollte klar sein, dass die letzten drei Zeilen für Alice suboptimal sind, da wegen Monotonie $$ gilt. Alice darf $$ also in $$ zerlegen, wie sie will, sollte aber tunlichst $$ wählen. Was haben wir aus unserem Beispielzug gelernt?

Doch halt! Wir haben etwas vergessen! Alice kann natürlich auch $$ anfragen, also das rechte Intervall zerlegen:

Alice zerlegt das rechte Interval und erhält drei Intervalle mit Längen $$. Welches Paar wählt Eve? Das hängt davon ab, ob $$ oder $$ größer ist. Führen wir eine Konvention ein: $$, das linke Interval ist mindestens so groß wie das rechte; so sieht es auf den Bildern ja auch aus. Dann gilt natürlich auch $$ und somit $$ und $$. Eve wählt also das erste Paar: $$.

Ich behaupte, dass dieser Zug von Alice nicht optimal ist. Was, wenn Sie statt $$ den Index $$ angefragt hätte? Dann hätte sie das Tripel $$ bekommen und Eve hätte sich zwischen $$ und $$ entscheiden müssen. Beide Paare sind für Alice besser kleiner als $$: $$ Wir folgern: optimalerweise zerlegt Alice immer das größere der beiden Intervalle. Wir können nun alles zusammenfassen in folgender rekursiver Formel:

Nochmal in Worten und in einem Beispiel: in jedem Schritt ist es ziemlich offensichtlich, welches der optimale Schritt für Eve ist; wir ersetzen die Spielerin Eve also durch eine starre Regel und haben nun ein Spiel mit nur einer Spielerin: Alice. Es ist also ein Solitaire-Spiel, in welchem Alice in Zahlenpaar $$ gegeben hat und auf weitere, kleinere Paare "ziehen" kann, bis sie das Paar $$ erreicht hat. Ein Spielverlauf, startend von $$, könnte also folgendmaßen aussehen:

Die Werte $$

Gleiche Werte eingefärbt

Die Ecken der Farbklassen.

Die Ecken einer Farbklasse kommen in Paaren, z.B. $$ und $$ für die Farbklasse 4. Das ist nicht überraschend, haben wir doch bereits früh die Symmetrie $$ bemerkt. Die Menge $$ also die Menge aller eingefärbten Zellen, schaut aus wie zwei übereinandergelegte Rechtecke, nämlich der Dimensionen $$ und $$. Und in der Tat: Sehen wir uns diese Dimensionen, bzw. die Koordinaten der Eckpunkte genauer an: $$ Vielleicht "klingelt" es jetzt bei Ihnen. Dies sind die berühmten Fibonacci-Zahlen $$ mit dem rekursiven Bildungsgestzt $$ Jetzt sind wir bereit für den vorletzten Schritt bei der Suche nach einem Beweis.

Formulieren Sie eine Vermutung. In unserem Falle heißt die Vermutung: die "Ecken" unserer Wertebereiche haben die Koordinaten $$ bzw. $$. Um das mathematisch ganz präzise auszudrücken, müssen wir noch den Zusammenhang zwischen $$ und dem "Wert" $$ herausfinden. Zum Beispiel hat die eine Ecke von $$ die Koordinaten $$. Wir sind nun bereit, eine Vermutung zu formulieren.

Dies ist die "einfache" Richtung, weil wir hier konkret eine Strategie für Alice angeben können.

Dies ist die "schwierigere" Richtung, weil wir hier alle möglichen Züge von Alice berücksichtigen müssen.

Mit Behauptung 1 und Behauptung 2 haben wir beide Richtungen des "genau dann, wenn"-Satzes gezeigt und beschließen somit den Beweis des Theorems. $$

Um zu zeigen, dass Alice im Worst-Case auch tatsälich $$ Anfragen benötigt, drehen wir die Dinge um: wir nehmen an, dass es Alice mit $$ Anfragen schafft und zeigen, dass $$ gelten muss. Sei nun $$ der erste Index, den Alice anfragt. Damit erhält sie zwei Intevalle der Längen $$ und $$. Da wir nicht wissen, ob $$ oder $$ größer ist, führen wir zwei neue Bezeichner ein: $$ und $$. Jetzt gilt auf jeden Fall $$ und $$. Da Alice $$ weitere Zugriffe macht, also $$, gilt nach Theorem $$ und somit $$, wie behauptet. $$