Pythonで株式の保有と売却により得られる最大利益を求めるプログラム

時系列順に並べられた企業の株価リスト nums が与えられたとします。1日につき最大1株まで購入でき、複数の銘柄を同時に保有することや、任意のタイミングで売却することが可能です。この条件のもとで、獲得できる利益の最大値を求めてください。

たとえば、入力が nums = [3, 4, 7, 3, 5] の場合、出力は 9 になります。具体的には、価格が 3 と 4 のときにそれぞれ 1 株ずつ購入し、価格が 7 になった時点で両方とも売却します。その後、再び価格が 3 のときに購入し、価格が 5 のときに売却します。合計利益は (7 − 3) + (7 − 4) + (5 − 3) = 9 です。

解法の考え方

この問題は、リストを末尾から走査する貪欲法（グリーディーなアプローチ）で解くことができます。ポイントは「将来の高値よりも安い価格で買った株は、すべてその高値で売却するのが最適」という性質です。

具体的な手順は以下の通りです。

1. 答えとなる変数 ans を 0 で初期化します。
2. nums が空になるまで、次の処理を繰り返します。
   • nums の末尾の要素を取り出し、top とします。
   • nums が空ではなく、かつ top が末尾の要素より大きい間、次を繰り返します。
     • ans に (top − 末尾の要素) を加算します。
     • nums の末尾の要素を削除します。
3. ans を返します。

実装例

以下にPythonでの実装例を示します。

def solve(nums):
    ans = 0
    while nums:
        top = nums.pop()
        while nums and top > nums[-1]:
            ans += top - nums.pop()

    return ans

nums = [3, 4, 7, 3, 5]
print(solve(nums))

入力

[3, 4, 7, 3, 5]

出力

9

計算量について

各要素は最大でも1回しか追加・削除されないため、時間計算量は O(n)、必要な追加メモリは O(1) で済みます。株価データが長くなっても効率的に動作するのが特徴です。