In meinem ständigen Bestreben, meine LeetCode-Fähigkeiten zu verbessern, habe ich mich mit dem Problem „Bester Zeitpunkt zum Kauf und Verkauf von Aktien II“ befasst. Diese Herausforderung ist eine Weiterentwicklung des klassischen Problems „Best Time to Buy and Sell Stock II“ (LeetCode 121), jedoch mit einem entscheidenden Unterschied: *Sie können mehrere Transaktionen ausführen, um den Gewinn zu maximieren.
*

Ein visueller Ansatz

Bevor ich in den Code eintauchte, fand ich es unglaublich hilfreich, das Problem auf einem Whiteboard zu visualisieren. Dadurch konnte ich das Problem in kleinere, besser überschaubare Schritte unterteilen.

Der gierige Ansatz

Angesichts der Flexibilität, unbegrenzte Transaktionen durchzuführen, schien ein gieriger Ansatz vielversprechend. Die Grundidee ist einfach: Immer wenn der Kurs einer Aktie im Vergleich zum Vortag steigt, betrachten wir dies als potenzielle Gewinnchance. Indem wir alle diese Preisunterschiede addieren, berechnen wir effektiv den maximalen Gewinn.

Python-Implementierung

Hier ist der Python-Code, der diese gierige Strategie implementiert:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0

        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                profit =prices[i] - prices[i-1]

        return profit

JavaScript-Implementierung

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var profit = 0;
    for (var i = 1; i  prices[i-1])
    {
        profit  = Number(prices[i] - prices[i-1])
    }
    }

    return profit
};

Zeit- und Raumkomplexität

• Die zeitliche Komplexität dieses Ansatzes beträgt O(N), wobei N = Länge des Arrays.
• Die Raumkomplexität beträgt N(1), da wir an Ort und Stelle vergleichen.