Sortieralgorithmus mit Divide and Conquer

Question

Dies ist wie ein Lager-Marketing-Problem, ich bin verwirrt, dass die Frage nach dem täglichen maximalen Gewinn zu fragen ist? Ich weiß nur, dass die Zeitkomplexität des Algorithmus O (n) oder O (n log2 n) sein kann.

Die Eingabe ist A, eine Reihe von Aktienkursen. Für Tag I ist der beste Handel der maximale Gewinn, der durch Kauf am Tag i und Verkauf an einem nachfolgenden Tag erzielt werden kann. Aus Bequemlichkeit können Sie den besten Handel für den letzten Tag definieren, um einfach A [n] zu sein (denn wenn Sie am letzten Tag kaufen, können Sie nicht verkaufen und Sie haben Ihr ganzes Geld verloren). Geben Sie den Pseudocode eines Algorithmus, der ein Array mit dem maximalen Gewinn für jeden Tag in A zurückgibt.

Update: Ich verstehe, wie Sie jetzt den maximalen Gewinn erhalten, und ich kann den ähnlichen Algorithmus wie die Merge-Sortierung verwenden und erobere, um diesen maximalen Gewinn zu finden. Meine Frage ist, was ist eine andere Methode (Algorithmus), die die Zeitkomplexität O (n) verwendet, um den maximalen Gewinn zu finden oder wie kann ich auf diese Weise vorgehen?

Answer 1

Eine Möglichkeit, dieses Problem denken kann, ist eine for-Schleife, da es O (n) ist, kann ich Ihnen ein paar Hinweise geben:

for i from 0 to n: 
     if (A[i] < A[min]) // find the minimum value of stock 
      min = i; 
     profit = A[i] - A[min] // get the profit 
     if (profit > maxProfit) { // compares the profits 
      maxProfit = profit // always update the max profit 

Answer 2

Wenn Sie am Tag kaufen i, der maximale Gewinn Sie machen können, ist Amax(i) - A[i], wo Amax(i) der höchste Preis ist, die inach Tage tritt. Mein Lesen der Spezifikation des Algorithmus ist, dass Sie das Array M konstruieren und zurückgeben, deren Einträge durch M[i] = Amax(i) - A[i] definiert sind.

Der höchste Preis, der nach dem Tag i desto größer ist der A[i+i] und dem höchsten Preis, der i + 1 Tag auftritt auftritt.

Der letzte Absatz gibt Ihnen eine rekursive Beziehung, mit der Ausnahme, dass im Gegensatz zu die „typischen“ Rekursion Sie könnten, der i te Wert ist abhängig von dem i + 1 st Wert, anstatt umgekehrt sehen. Aber zum Glück für Sie wissen Sie bereits, dass n th Wert und jeder spätere Wert ist 0, das heißt, nach Tag n erhalten Sie 0 für Ihre Aktie. Sie müssen also nur die Werte für Tage 1, 2, ..., n - 1 herausfinden, die Sie in O (n) Zeit tun können. Und jedes Mal, wenn Sie einen dieser Werte finden, Amax(i), können Sie einen der Einträge M mit M[i] = Amax(i) - A[i] festlegen.

---

Wenn Sie den maximalen Gewinn zu finden, die an einem einzigen Tag durch den Kauf und Verkauf von an einem späteren Tag einen Anteils der Aktien vorgenommen werden können, eine Zeit (obwohl dies nicht von der Problemstellung erforderlich ist, so weit ich sehen kann), müssen Sie nur den maximalen Wert in M finden, was Sie in O (n) Zeit tun können.

Wenn Ihr Ziel ist, den maximalen Gewinn durch eine Reihe von Aktionen zu ermöglichen, Kauf und Verkauf von Aktien, ist das Beste, was Sie tun können, so viele Aktien wie möglich zu kaufen, wenn die Aktie auf einem lokalen Minimum ist unendlichen Preis vor dem ersten Tag) und verkaufen alles, wenn es einen lokalen Höchstpreis erreicht. Sie können alle lokalen Minima und Maxima in O (n) Zeit identifizieren, A in beide Richtungen scannen, und einen Startbetrag des Geldes geben, können Sie den maximalen Gesamtgewinn in O (n) Zeit unter Verwendung der Liste der lokalen Minima und berechnen Höchstwerte von A. (Dies verwendet jedoch nicht das Array, das Sie von der ursprünglichen Problembeschreibung angefordert hatten, da dieses Array weder die Anzahl der gekauften Aktien noch die Möglichkeit mehrerer Transaktionen berücksichtigt.)

Denken Sie daran, dass, wenn jeder Durchlauf eines Zwei-Durchlauf-Algorithmus O (n) -Zeit benötigt, der Algorithmus als Ganzes eine O (n) -Zeit benötigt.