Déchiffrer le LeetCode. Meilleur moment pour acheter et vendre des actions II

Dans ma quête continue pour perfectionner mes compétences LeetCode, j'ai abordé le problème du « Meilleur moment pour acheter et vendre des actions II ». Ce défi fait suite au problème classique « Meilleur moment pour acheter et vendre des actions II » (LeetCode 121) mais avec une différence cruciale : *vous pouvez exécuter plusieurs transactions pour maximiser les profits.
*

Une approche visuelle

Avant de plonger dans le code, j'ai trouvé incroyablement utile de visualiser le problème sur un tableau blanc. Cela m'a permis de décomposer le problème en étapes plus petites et plus gérables.

L’approche gourmande

Compte tenu de la possibilité d'effectuer des transactions illimitées, une approche gourmande semblait prometteuse. L’idée de base est simple : chaque fois que le prix d’une action augmente par rapport à la veille, nous considérons cela comme une opportunité potentielle de profit. En additionnant toutes ces différences de prix, nous calculons effectivement le profit maximum.

Implémentation Python

Voici le code Python qui implémente cette stratégie gourmande :

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

Implémentation JavaScript

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

    return profit
};

Complexité temporelle et spatiale

• La complexité temporelle de cette approche est O(N) où N = longueur du tableau.
• La complexité spatiale est N(1) car nous comparons sur place.

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!