NeetCodeのSolutionを書いていく

#

Best Time to Buy and Sell Stock

#

株価を想定した、整数の配列を渡されるので、安いときに買って高いときに売る。 最高の利益を出せばOK。 明記されていないけど、複数回売り買いしていいのかな？

[7,1,5,3,6,4] の場合、複数回売り買いした時の最適値は(5-1)+(6-3)で7なので1回だけみたい。

ポイントは売るときに未来の値段では買えないことくらいかな？

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy = 100
        profit = 0
        for price in prices:
            if buy > price:
                buy = price
            if profit < price - buy:
                profit = price - buy
            print(price, buy, profit)
        return profit

いけたー。 最初に問題設定を読み誤って(明記されていない？)すこ手こずってしまった。 問題設定確認とアルゴリズムの事前検討大事。