Best Time to Buy and Sell Stock

Vous obtenez le prix d’une action sur une série de jours, avec un prix par jour. Vous pouvez acheter une action un jour et la vendre un jour ultérieur. Le profit correspond au prix de vente moins le prix d’achat, et vous voulez obtenir le profit le plus élevé possible. Si chaque transaction vous ferait perdre de l’argent, vous ne faites tout simplement aucune transaction et gagnez 0.

Prenez les prix [7, 2, 5, 9, 1, 4]. Acheter à 2 le jour 1 et vendre à 9 le jour 3 rapporte 7, et aucune autre paire de jours ne fait mieux. Acheter à 1 le jour 4 semble tentant, car c’est le jour le moins cher, mais le seul jour ultérieur où vendre est le jour où le prix est de 4, cette transaction ne rapporte donc que 3.

Essayer chaque paire de jours fonctionne, mais c’est beaucoup trop lent pour de longues listes de prix. Vous pouvez plutôt parcourir les jours une seule fois. Si vous vendez aujourd’hui, le meilleur jour pour avoir acheté est le jour le moins cher jusqu’à présent : gardez donc en mémoire le prix le plus bas au fil des jours. Le meilleur profit d’aujourd’hui est le prix d’aujourd’hui moins le prix le plus bas, et la réponse est le plus grand de ces profits.

Écris une fonction nommée maxProfit qui reçoit une liste d’entiers prices, où prices[i] est le cours de l’action le jour i, et renvoie le profit maximal que tu peux réaliser en achetant un jour et en vendant un jour ultérieur. Si aucune transaction ne rapporte de profit, renvoie 0.

Contraintes : 1 ≤ prices.length ≤ 10^5, 0 ≤ prices[i] ≤ 10^4.