Pythonで手数料を考慮した株式売買の最大利益を求めるプログラム

ある企業の時系列順に並んだ株価リストと、1回の売却取引にかかる手数料が与えられているとします。この株を何度でも自由に売買した場合に得られる最大の利益を求めるのが本記事の目的です。ただし、売却する前に必ずその株を購入していなければならないという制約があります。

問題の例

たとえば、入力が prices = [2, 10, 4, 8]、fee = 3 の場合を考えてみましょう。このときの出力は 6 になります。

• まず 2 で株を買い、10 で売却します。手数料として 3 がかかるため、利益は 10 − 2 − 3 = 5 です。
• 次に 4 で再度株を買い、8 で売却します。ここでも手数料 3 がかかるため、利益は 8 − 4 − 3 = 1 です。
• 合計利益は 5 + 1 = 6 となります。

解法のアプローチ

この問題は、再帰関数を使って各時点での「保有中」か「未保有」かの状態を追跡することで解けます。具体的な手順は以下の通りです。

• n := 株価リスト prices のサイズとします。
• 関数 recur() を定義します。引数は i := 0(現在の日付インデックス)、flag := 0(株を保有していない状態)とします。
• i が n と等しい場合(すべての日付を処理し終えた場合)、0 を返します。
• flag が偽(株を保有していない)の場合、以下の2つのうち大きい方を返します。
  • recur(i + 1, 1) − prices[i](この日で株を買う場合)
  • recur(i + 1, 0)(この日は何もせずスキップする場合)
• flag が真(株を保有している)の場合、以下の2つのうち大きい方を返します。
  • recur(i + 1, 1)(保有を続ける場合)
  • recur(i + 1, 0) + prices[i] − fee(この日で売却する場合)
• メインメソッドから recur() を呼び出します。

実装例

それでは、実際のコードを見て理解を深めましょう。

サンプルコード

class Solution:
    def solve(self, prices, fee):
        n = len(prices)

        def recur(i=0, flag=0):
            if i == n:
                return 0
            if not flag:
                return max(recur(i + 1, 1) - prices[i], recur(i + 1, 0))
            return max(recur(i + 1, 1), recur(i + 1, 0) + prices[i] - fee)

        return recur()

ob = Solution()
prices = [2, 10, 4, 8]
fee = 3
print(ob.solve(prices, fee))

入力

[2, 10, 4, 8], 3

出力

6

補足：計算量について

上記の再帰的なアプローチは直感的で分かりやすい一方、日数 n が増えると計算量が指数的に増大する可能性があります。実務的には、メモ化(キャッシュ)や動的計画法(DP)を組み合わせることで、O(n) の時間計算量まで最適化できます。また、「売却時にのみ手数料が発生する」という条件を活かし、各日の「株を保有しているときの最大利益」と「保有していないときの最大利益」を2つの変数で逐次更新していく手法もよく使われます。