Pythonで最大k回の売買から得られる最大利益を求めるプログラム

時系列順に並んだ企業の株価リスト nums と、売買の最大回数 k が与えられているとします。このとき、最大で k 回の買いと売り(必ず「買う→売る→買う→売る」の順序を守る)から得られる最大利益を求めるのが本記事の目的です。

例えば、prices = [7, 3, 5, 2, 3]、k = 2 という入力の場合、出力は 3 になります。これは、3 で買って 5 で売り、その後 2 で買って 3 で売ることで、利益 (5 − 3) + (3 − 2) = 3 を得られるためです。

解法のアプローチ

この問題は動的計画法(DP)の考え方を使って解くことができます。手順は以下の通りです。

• 関数 dp(i, k, bought) を定義します。i は現在の日付、k は残りの取引可能回数、bought は株を保有中かどうかを表す真偽値です。
• i が prices のサイズと等しい、または k が 0 の場合は、これ以上取引できないため 0 を返します。
• bought が True の場合(株を保有している状態)は、「今日売却する(dp(i+1, k-1, False) + prices[i])」か「売らずに翌日へ持ち越す(dp(i+1, k, bought))」のうち大きい方を返します。
• bought が False の場合(株を保有していない状態)は、「今日購入する(dp(i+1, k, True) - prices[i])」か「買わずに翌日へ進む(dp(i+1, k, bought))」のうち大きい方を返します。
• メイン処理から dp(0, k, False) を呼び出し、その結果を返します。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, prices, k):
        def dp(i, k, bought):
            if i == len(prices) or k == 0:
                return 0
            if bought:
                return max(dp(i + 1, k - 1, False) + prices[i], dp(i + 1, k, bought))
            else:
                return max(dp(i + 1, k, True) - prices[i], dp(i + 1, k, bought))

        return dp(0, k, False)

ob = Solution()
prices = [7, 3, 5, 2, 3]
k = 2
print(ob.solve(prices, k))

入力

[7, 3, 5, 2, 3], 2

出力

3

補足：計算量について

上記の素朴な再帰実装は、状態の組み合わせが増えると指数的に計算量が膨らむ可能性があります。実務では functools.lru_cache デコレータや辞書によるメモ化を追加することで、各状態 (i, k, bought) の計算を一度だけ行うようにでき、計算量を O(n × k) まで抑えられます。大きな入力に対してはメモ化の導入を検討するとよいでしょう。