C++で株式の売買から得られる最大利益を計算する方法

この問題では、i日目の株価を表す配列 stkprice[] が与えられ、C++で株式の売買によって得られる最大利益を計算するプログラムを作成します。

問題の概要

ここで求められているのは、いつ株を買い、いつ売れば利益を最大化できるかを見極めることです。利益を生むためには、株価が安いときに購入し、価格が上昇したタイミングで売却します。その後、再び価格が下落した局面が現れたら、同じ売買サイクルを繰り返します。

具体例を使って問題を理解しましょう。

入力

stkprice[] = {120, 310, 405, 210, 150, 550}

出力

685

説明

1日目に購入して3日目に売却すると、285の利益が得られます。

続いて、5日目に購入して6日目に売却すると、400の利益が得られます。

したがって、合計利益は (285 + 400) = 685 となります。

解法アプローチ1：すべての売買パターンを調べる

最も単純な解法は、考えられるすべての売買サイクルの組み合わせを確認する方法です。各日を起点として「その日に買って、それ以降のいずれかの日に売る」パターンをすべて試し、最大の利益をもたらす組み合わせを採用します。ただし、この方法はデータ数が増えると計算量が急増するため、実用的とは言えません。

この解法の動作を示すプログラムは以下の通りです。

例

#include <iostream>
using namespace std;
int max(int a, int b){
    if(a > b)
        return a;
    return b;
}
int MaximizeProfit(int stkPrice[], int firstDay, int lastDay){
    if (lastDay <= firstDay)
        return 0;
    int maxProfit = 0;
    for (int i = firstDay; i < lastDay; i++) {
        for (int j = i + 1; j <= lastDay; j++) {
            if (stkPrice[j] > stkPrice[i]) {
                int profit = ( stkPrice[j] - stkPrice[i] ) + MaximizeProfit(stkPrice, firstDay, i - 1) + MaximizeProfit(stkPrice, j + 1, lastDay);
                maxProfit = max(maxProfit, profit);
            }
        }
    }
    return maxProfit;
}
int main(){
    int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
    int days = 6 ;
    cout<<"The Maximum profit is "<<MaximizeProfit(stkPrice, 0, days);
    return 0;
}

出力

The Maximum profit is 685

解法アプローチ2：局所的な最小値・最大値を利用する効率的な方法

より効率的な解法は、各取引ごとの利益を個別に最大化することで、全体の最大利益を導き出すものです。これは、株価の推移における局所的な最小値（谷）と最大値（山）を見つけることで実現できます。

局所的最小値とは、前日と翌日のどちらの株価よりも低い日のことです。局所的最大値はその逆です。もし（インデックス0からn-2の範囲に）局所的最小値が存在しない場合、利益を得られる機会はありません。

利益を最大化するには、局所的最小値の日株を買い、次に現れる局所的最大値の日売却します。この操作をすべての最小値・最大値のペアに対して行い、それぞれの利益を合計すれば、最大利益が求まります。この方法は配列を一度走査するだけで済むため、線形時間 O(n) で処理できる点が大きな利点です。

この解法の動作を示すプログラムは以下の通りです。

例

#include <iostream>
using namespace std;
void MaximizeProfit(int price[], int n){
    if (n == 1)
        return;
    int maxProfit = 0;
    int i = 0;
    while (i <= n - 1) {
        while ((i <= n - 2) && (price[i + 1] <= price[i]))
            i++;
        int minima = i++;
        while ((i < n) && (price[i] >= price[i - 1]))
            i++;
        int maxima = i - 1;
        maxProfit += (price[maxima] - price[minima]);
        // 各最小値・最大値サイクルの利益を表示したい場合はコメントを外す
        //cout <<"Stock bought on day "<<(minima+ 1 )<<" and Sold on day "<<(maxima+1) <<" at a profit of "<<(price[maxima] - price[minima] )<<"\n";
    }
    cout<<"The maximized profit is "<<maxProfit;
}
int main(){
    int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
    int days = 6;
    MaximizeProfit(stkPrice, days);
    return 0;
}

出力

The maximized profit is 685

まとめ

全組み合わせを調べる力任せの手法は理解しやすい一方で計算コストが高く、局所的な最小値・最大値を追跡する手法は1回の走査で答えを得られるため、実務や競技プログラミングでは後者が推奨されます。株価のような時系列データを扱う際は、「安く買って高く売る」局面を極値のペアとして捉える発想が非常に有効です。