最大2回の株式売買で得られる最大利益の求め方

株式トレーディングにおいて、ある投資家が朝に株を買い、夕方に売るという取引を行います。1日に行える取引は最大2回までとし、2回目の取引は必ず1回目の取引が完了した後にのみ開始できるものとします。与えられた株価データをもとに、投資家が獲得できる最大の利益を求めるのがこの問題です。

入力と出力

入力：
株価リスト {2, 30, 15, 10, 8, 25, 80}

出力：
合計利益は 100 となります。
価格2で購入し価格30で売却 → 利益 28
その後、価格8で購入し価格80で売却 → 利益 72
よって合計利益は 28 + 72 = 100

アルゴリズムの考え方

この問題は動的計画法（DP）を使うことで効率的に解けます。ポイントは、配列を後ろからと前からの2方向に走査することです。

1. 後ろからの走査： 各時点i以降で売却した場合の1回目の取引による最大利益 profit[i] を求めます。そのために、それ以降に出現する最高値 maxPrice を管理しながら、「これまでの最大利益」と「最高値との差額」の大きい方を記録していきます。
2. 前からの走査： 各時点i以前で購入できる最低値 minPrice を管理しながら、「1回目の取引の利益＋2回目の取引の利益」の合計を更新し、最終的な最大利益を求めます。

findMaxProfit(pricelist, n)

入力 − すべての株価のリストと、リスト内の要素数。
出力 − 最大利益。

Begin
    define profit array of size n and fill with 0
    maxPrice := pricelist[n-1]        // 最後の要素を選択

    for i := n-2 down to 0, do
       if pricelist[i] > maxPrice, then
          maxPrice := pricelist[i]
       profit[i] := maximum of profit[i+1] and maxPrice – pricelist[i]
    done

    minPrice := pricelist[0]          // 最初の要素を選択
    for i := 1 to n-1, do
       if pricelist[i] < minPrice, then
          minPrice := pricelist[i]
       profit[i] := maximum of profit[i-1] and (profit[i] + (pricelist[i] - minPrice))
    done

    return profit[n-1]
End

C++での実装例

#include<iostream>
using namespace std;

int max(int a, int b) {
    return (a>b)?a:b;
}

int findMaxProfit(int priceList[], int n) {
    int *profit = new int[n];
    for (int i=0; i<n; i++)      // 利益配列を0で初期化
        profit[i] = 0;

    int maxPrice = priceList[n-1];   // 株価リストの最終要素で初期化

    // 後ろから走査し、各時点での1回目の取引の最大利益を求める
    for (int i=n-2;i>=0;i--) {
        if (priceList[i] > maxPrice)
            maxPrice = priceList[i];

        profit[i] = max(profit[i+1], maxPrice - priceList[i]);
    }

    int minPrice = priceList[0];     // 株価リストの最初の要素を最小値として初期化

    // 前から走査し、2回目の取引の利益を加算して最大利益を更新
    for (int i=1; i<n; i++) {
        if (priceList[i] < minPrice)
            minPrice = priceList[i];

        profit[i] = max(profit[i-1], profit[i] + (priceList[i]- minPrice) );
    }

    int result = profit[n-1];
    return result;
}

int main() {
    int priceList[] = {2, 30, 15, 10, 8, 25, 80};
    int n = 7;
    cout << "Maximum Profit = " << findMaxProfit(priceList, n);
}

実行結果

Maximum Profit = 100

計算量について

このアルゴリズムは配列を2回走査するだけで済むため、時間計算量は O(n)、補助配列として利益表を1つ持つため空間計算量も O(n) となります。全ての売買タイミングの組み合わせを総当たりで調べる方法（O(n²)以上）と比べて大幅に高速であり、株価データの件数が多い場合でも実用的な速度で処理できます。