LeetCode のスキルを磨くという継続的な探求の中で、私は「株式の売買に最適な時期 II」の問題に取り組みました。この課題は古典的な「株式の売買に最適な時期 II」問題 (LeetCode 121) のフォローアップですが、決定的な違いがあります: *利益を最大化するために複数のトランザクションを実行できます。
*

視覚的なアプローチ

コードに入る前に、ホワイトボード上で問題を視覚化することが非常に役立つことがわかりました。これにより、問題をより小さく、より管理しやすいステップに分割することができました。

貪欲なアプローチ

無制限にトランザクションを実行できる柔軟性を考えると、貪欲なアプローチが有望であるように思えました。中心となる考え方はシンプルです。株価が前日と比較して上昇するたびに、それは潜在的な利益の機会であると考えられます。これらすべての価格差を合計することで、最大利益が効率的に計算されます。

Pythonの実装

この貪欲な戦略を実装する Python コードは次のとおりです:

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

JavaScriptの実装

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

    return profit
};

時間と空間の複雑さ

• このアプローチの時間計算量は O(N) です (N = 配列の長さ)。
• その場で比較しているため、空間複雑度は N(1) です。