LeetCode DayDynamic Programming Teil8

121. Beste Zeit zum Kaufen und Verkaufen von Aktien

Sie erhalten eine Reihe von Preisen, wobei „Preise[i]“ der Preis einer bestimmten Aktie am i-ten Tag ist.

Sie möchten Ihren Gewinn maximieren, indem Sie einen einzigen Tag für den Kauf einer Aktie und einen anderen Tag in der Zukunft für den Verkauf dieser Aktie auswählen.

Geben Sie den maximalen Gewinn zurück, den Sie mit dieser Transaktion erzielen können. Wenn Sie keinen Gewinn erzielen können, geben Sie 0 zurück.

Beispiel 1:

Eingabe: Preise = [7,1,5,3,6,4]
Ausgabe: 5
Erläuterung: Kaufen Sie am 2. Tag (Preis = 1) und verkaufen Sie am 5. Tag (Preis = 6), Gewinn = 6-1 = 5.
Beachten Sie, dass der Kauf am 2. Tag und der Verkauf am 1. Tag nicht zulässig sind, da Sie vor dem Verkauf kaufen müssen.
Beispiel 2:

Eingabe: Preise = [7,6,4,3,1]
Ausgabe: 0
Erläuterung: In diesem Fall werden keine Transaktionen durchgeführt und der maximale Gewinn = 0.

Einschränkungen:

1 <= Preise.Länge <= 10^5
0 <= Preise[i] <= 10^4
Originalseite

Methode 1, Greedy-Algorithmen

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        int profit = 0;
        int buy = prices[0];
        for(int i=1; i<prices.length; i++ ){
            if(buy>=prices[i]){
                buy = prices[i];
            }else{
                profit = Math.max(profit, prices[i]-buy);
            }
        }
        return profit;
    }



</p>
<p>Zeit O(n) Raum O(1)</p>
<h2>
  
  
  Methode 2 Dynamische Programmierung
</h2>


<pre class="brush:php;toolbar:false">    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        // 2 means we have 2 different status (have owned stock or not )
        int[][] dp = new int[prices.length][2];

        // if we want to own the stock we should pay for the specific price
        dp[0][0] = -prices[0];
        for(int i=1; i<dp.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], prices[i] + dp[i-1][0]);
        }
        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[dp.length-1][1];
    }

Zeit O(n) Raum O(n)
Dynamische Programmierung ist allgemeiner als gierige Algorithmen, da sie nicht nur für das spezifische Problem funktioniert.

Methode 2.1 (Verbesserung der Raumkomplexität)

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        // 2 means we have 2 different status (have owned stock or not )
        int[] dp = new int[2];

        // if we want to own the stock we should pay for the specific price
        dp[0] = -prices[0];
        for(int i=1; i<prices.length; i++){
            dp[1] = Math.max(dp[1], prices[i] + dp[0]);
            dp[0] = Math.max(dp[0], -prices[i]);
        }
        // 
        return dp[1];
    }

Seien Sie hier vorsichtig, wir sollten dp[1] zuerst verarbeiten, da es das vorherige dp[0] anstelle des aktualisierten dp[0] verwendet.

122. Beste Zeit zum Kaufen und Verkaufen von Aktien II

Sie erhalten ein ganzzahliges Array von Preisen, wobei „Preise[i]“ der Preis einer bestimmten Aktie am i-ten Tag ist.

An jedem Tag können Sie entscheiden, die Aktie zu kaufen und/oder zu verkaufen. Sie können jeweils nur höchstens eine Aktie halten. Sie können es jedoch kaufen und dann noch am selben Tag sofort verkaufen.

Finden und erzielen Sie den maximalen Gewinn, den Sie erzielen können.

Beispiel 1:

Eingabe: Preise = [7,1,5,3,6,4]
Ausgabe: 7
Erläuterung: Kaufen Sie am 2. Tag (Preis = 1) und verkaufen Sie am 3. Tag (Preis = 5), Gewinn = 5-1 = 4.
Dann kaufen Sie am 4. Tag (Preis = 3) und verkaufen am 5. Tag (Preis = 6), Gewinn = 6-3 = 3.
Der Gesamtgewinn beträgt 4 + 3 = 7.
Beispiel 2:

Eingabe: Preise = [1,2,3,4,5]
Ausgabe: 4
Erläuterung: Kaufen Sie am Tag 1 (Preis = 1) und verkaufen Sie am Tag 5 (Preis = 5), Gewinn = 5-1 = 4.
Der Gesamtgewinn beträgt 4.
Beispiel 3:

Eingabe: Preise = [7,6,4,3,1]
Ausgabe: 0
Erläuterung: Es gibt keine Möglichkeit, einen positiven Gewinn zu erzielen, daher kaufen wir niemals die Aktie, um den maximalen Gewinn von 0 zu erzielen.

Einschränkungen:

1 <= Preise.Länge <= 3 * 10……4
0 <= Preise[i] <= 10……4

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }

        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[i][0] = Math.max(dp[i-1][1]-prices[i], dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][0]+prices[i], dp[i-1][1]);
        }

        return dp[prices.length-1][1];
    }

Die Rolling-Array-Methode

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }

        int[] dp = new int[2];
        dp[0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[1] = Math.max(dp[0]+prices[i], dp[1]);
            dp[0] = Math.max(dp[1]-prices[i], dp[0]);

        }

        return dp[1];
    }

123. Beste Zeit zum Kaufen und Verkaufen von Aktien III

Sie erhalten eine Reihe von Preisen, wobei „Preise[i]“ der Preis einer bestimmten Aktie am i-ten Tag ist.

Finden Sie den maximalen Gewinn, den Sie erzielen können. Sie können höchstens zwei Transaktionen abschließen.

Hinweis: Sie dürfen nicht mehrere Transaktionen gleichzeitig durchführen (d. h. Sie müssen die Aktie verkaufen, bevor Sie erneut kaufen).

Beispiel 1:

Eingabe: Preise = [3,3,5,0,0,3,1,4]
Ausgabe: 6
Erläuterung: Kaufen Sie am Tag 4 (Preis = 0) und verkaufen Sie am Tag 6 (Preis = 3), Gewinn = 3-0 = 3.
Dann kaufen Sie am 7. Tag (Preis = 1) und verkaufen am 8. Tag (Preis = 4), Gewinn = 4-1 = 3.
Beispiel 2:

Eingabe: Preise = [1,2,3,4,5]
Ausgabe: 4
Erläuterung: Kaufen Sie am Tag 1 (Preis = 1) und verkaufen Sie am Tag 5 (Preis = 5), Gewinn = 5-1 = 4.
Beachten Sie, dass Sie nicht am ersten Tag kaufen, am zweiten Tag kaufen und später verkaufen können, da Sie mehrere Transaktionen gleichzeitig durchführen. Sie müssen verkaufen, bevor Sie erneut kaufen.
Beispiel 3:

Eingabe: Preise = [7,6,4,3,1]
Ausgabe: 0
Erläuterung: In diesem Fall wird keine Transaktion durchgeführt, d. h. maximaler Gewinn = 0.

Einschränkungen:

1 <= Preise.Länge <= 10^5
0 <= Preise[i] <= 10^5

    public int maxProfit(int[] prices) {
        int transactions = 2;
        int[][] dp = new int[prices.length][transactions*2+1];
        for(int i=1; i<=transactions; i++){
            dp[0][i*2-1] = -prices[0];
        }

        for(int i=1; i<prices.length; i++){

            dp[i][1] = Math.max(dp[i-1][0]-prices[i], dp[i-1][1]);
            dp[i][2] = Math.max(dp[i-1][1]+prices[i], dp[i-1][2]);
            dp[i][3] = Math.max(dp[i-1][2]-prices[i], dp[i-1][3]);
            dp[i][4] = Math.max(dp[i-1][3]+prices[i], dp[i-1][4]);
        }
        Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);

        return dp[prices.length-1][4];
    }

Das obige ist der detaillierte Inhalt vonLeetCode DayDynamic Programming Teil8. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!