Programmation dynamique LeetCode Day, partie 8

121. Meilleur moment pour acheter et vendre des actions

Vous recevez un tableau de prix où prix[i] est le prix d'une action donnée le ième jour.

Vous souhaitez maximiser votre profit en choisissant un seul jour pour acheter une action et en choisissant un autre jour dans le futur pour vendre cette action.

Rendez le profit maximum que vous pouvez réaliser grâce à cette transaction. Si vous ne pouvez réaliser aucun profit, renvoyez 0.

Exemple 1 :

Entrée : prix = [7,1,5,3,6,4]
Sortie : 5
Explication : Achetez le jour 2 (prix = 1) et vendez le jour 5 (prix = 6), profit = 6-1 = 5.
Notez qu'acheter le jour 2 et vendre le jour 1 n'est pas autorisé car vous devez acheter avant de vendre.
Exemple 2 :

Entrée : prix = [7,6,4,3,1]
Sortie : 0
Explication : Dans ce cas, aucune transaction n'est effectuée et le profit max = 0.

Contraintes :

1 <= prix.longueur <= 10^5
0 <= prix[i] <= 10^4
Page originale

Méthode 1, algorithmes gourmands

    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>temps O(n) espace O(1)</p>
<h2>
  
  
  Méthode 2 sur 3: Programmation dynamique
</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];
    }

temps O(n) espace O(n)
La programmation dynamique est plus générale que les algorithmes gloutons car elle ne fonctionnera pas uniquement pour un problème spécifique.

Méthode 2.1 (améliorer la complexité de l'espace)

    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];
    }

Soyez prudent ici, nous devons d'abord traiter dp[1] car il utilisera le dp[0] précédent au lieu du dp[0] mis à jour.

122. Meilleur moment pour acheter et vendre des actions II

Vous recevez un tableau de prix entiers où prix[i] est le prix d'une action donnée le ième jour.

Chaque jour, vous pouvez décider d'acheter et/ou de vendre des actions. Vous ne pouvez détenir qu’une seule action à la fois. Vous pouvez cependant l'acheter puis le revendre immédiatement le jour même.

Trouvez et restituez le profit maximum que vous pouvez réaliser.

Exemple 1 :

Entrée : prix = [7,1,5,3,6,4]
Sortie : 7
Explication : Achetez le jour 2 (prix = 1) et vendez le jour 3 (prix = 5), profit = 5-1 = 4.
Puis achetez le jour 4 (prix = 3) et vendez le jour 5 (prix = 6), profit = 6-3 = 3.
Le bénéfice total est de 4 + 3 = 7.
Exemple 2 :

Entrée : prix = [1,2,3,4,5]
Sortie : 4
Explication : Achetez le jour 1 (prix = 1) et vendez le jour 5 (prix = 5), profit = 5-1 = 4.
Le bénéfice total est de 4.
Exemple 3 :

Entrée : prix = [7,6,4,3,1]
Sortie : 0
Explication : Il n'y a aucun moyen de réaliser un profit positif, nous n'achetons donc jamais d'actions pour atteindre le profit maximum de 0.

Contraintes :

1 <= prix.longueur <= 3 * 10……4
0 <= prix[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];
    }

La méthode du tableau roulant

    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. Meilleur moment pour acheter et vendre des actions III

Vous recevez un tableau de prix où prix[i] est le prix d'une action donnée le ième jour.

Trouvez le profit maximum que vous pouvez réaliser. Vous pouvez effectuer au plus deux transactions.

Remarque : vous ne pouvez pas effectuer plusieurs transactions simultanément (c'est-à-dire que vous devez vendre l'action avant d'acheter à nouveau).

Exemple 1 :

Entrée : prix = [3,3,5,0,0,3,1,4]
Sortie : 6
Explication : Achetez le jour 4 (prix = 0) et vendez le jour 6 (prix = 3), profit = 3-0 = 3.
Puis achetez le jour 7 (prix = 1) et vendez le jour 8 (prix = 4), profit = 4-1 = 3.
Exemple 2 :

Entrée : prix = [1,2,3,4,5]
Sortie : 4
Explication : Achetez le jour 1 (prix = 1) et vendez le jour 5 (prix = 5), profit = 5-1 = 4.
Notez que vous ne pouvez pas acheter le jour 1, acheter le jour 2 et les vendre plus tard, car vous effectuez plusieurs transactions en même temps. Vous devez vendre avant d'acheter à nouveau.
Exemple 3 :

Entrée : prix = [7,6,4,3,1]
Sortie : 0
Explication : Dans ce cas, aucune transaction n'est effectuée, c'est à dire profit max = 0.

Contraintes :

1 <= prix.longueur <= 10^5
0 <= prix[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];
    }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!