【ITニュース解説】Lessons from LeetCode: Best Time to Buy and Sell Stock

LeetCodeは、プログラミングスキルを磨くためのオンラインプラットフォームだ。世界中のエンジニアが利用し、特にIT企業の採用面接におけるコーディング試験対策として非常に有名で、様々な種類のプログラミング問題が提供されている。これらを解くことで論理的思考力やアルゴリズムの知識を深めることができるのだ。

今回取り上げるのは「Best Time to Buy and Sell Stock（株を売買する最適な時期）」というクラシックな問題だ。これは、与えられた株価の時系列データから、一度だけ株を買い、一度だけ売ることで、最大の利益を出すにはどうすればよいかを求めるものだ。例えば、ある株の価格が日ごとに[7, 1, 5, 3, 6, 4]というように変動したと仮定しよう。このデータを見て、システムエンジニアは「いつ買って、いつ売れば一番儲かるか？」という問いに答えるアルゴリズムを設計する必要がある。この問題の重要な制約は、株は一度しか買えず、一度しか売れないという点、そして売る日は買う日より後でなければならないという点だ。

このような問題を効率的に解くために、「貪欲法（Greedy Algorithms）」と呼ばれるアルゴリズムがよく用いられる。貪欲法とは、その名の通り、各段階で目の前の状況において最も良いと思われる選択（局所的な最適解）を繰り返し行うことで、最終的により良い全体的な最適解に到達しようとする手法だ。常にその時点での最善を選び続けるため、直感的で比較的実装しやすいのが特徴である。ただし、常に貪欲法で全体的な最適解が得られるわけではなく、問題の性質によってはうまくいかないこともある。

この「Best Time to Buy and Sell Stock」問題においては、貪欲法が非常に効果的だ。どのように適用するかというと、株価のデータを最初から最後まで一度だけ見ていくことで、答えを導き出す。具体的には、二つの情報を常に記録しながら進める。一つは「これまでの最低購入価格（minimum price）」、もう一つは「これまでの最大利益（maximum profit）」だ。

アルゴリズムの動作はこうだ。まず、初期状態として最低購入価格を非常に大きな値（例えば、ありえないほど高い価格）に設定し、最大利益は0としておく。そして、与えられた株価データの一つ一つを順番に見ていく。ある日の株価に注目した時、まず、その日の株価がこれまでの最低購入価格を下回っていれば、最低購入価格をその日の株価に更新する。これは「もし今日株を買うなら、これがこれまでの間で一番安く買えるチャンスだ」と判断し、購入価格の候補を更新していることに相当する。次に、現在の株価からこれまでの最低購入価格を引いてみる。これが「もし今日、これまでの間で一番安く買った株を売るなら、これだけの利益が得られる」という額になる。この計算で得られた利益が、これまでの最大利益よりも大きければ、最大利益をその値に更新する。

例えば、先ほどの株価データ[7, 1, 5, 3, 6, 4]をこのアルゴリズムで追ってみよう。

1. 初期状態：最低購入価格は無限大、最大利益は0。
2. 一日目（株価7）：株価7は最低購入価格より低いので、最低購入価格を7に更新する。今日の株価7で売った場合の利益は7-7=0。最大利益は0のままだ。
3. 二日目（株価1）：株価1は最低購入価格7より低いので、最低購入価格を1に更新する。今日の株価1で売った場合の利益は1-1=0。最大利益は0のままだ。
4. 三日目（株価5）：株価5は最低購入価格1より高いため、最低購入価格1は変わらない。今日の株価5で売った場合の利益は5-1=4。この4は現在の最大利益0より大きいため、最大利益を4に更新する。
5. 四日目（株価3）：株価3は最低購入価格1より高いため、最低購入価格1は変わらない。今日の株価3で売った場合の利益は3-1=2。この2は現在の最大利益4より小さいため、最大利益は4のままだ。
6. 五日目（株価6）：株価6は最低購入価格1より高いため、最低購入価格1は変わらない。今日の株価6で売った場合の利益は6-1=5。この5は現在の最大利益4より大きいため、最大利益を5に更新する。
7. 六日目（株価4）：株価4は最低購入価格1より高いため、最低購入価格1は変わらない。今日の株価4で売った場合の利益は4-1=3。この3は現在の最大利益5より小さいため、最大利益は5のままだ。

すべての株価を見終わった時、最終的な最大利益は5となる。これは、二日目に株価1で買い、五日目に株価6で売ることで得られる利益に他ならない。

このシンプルなアプローチによって、一度のデータ走査（ループ）だけで最適な解を見つけることができる。システムエンジニアにとって、このように効率的なアルゴリズムを設計する能力は非常に重要だ。なぜなら、大規模なシステムやリアルタイム処理が必要な場面では、処理速度がシステムの性能に直結するからだ。もし非効率な方法で解こうとすると、データの量が増えるにつれて処理時間が膨大になり、システムが使い物にならなくなる可能性がある。

この問題を通じて、私たちは以下の重要な点を学ぶことができる。一つは、複雑に見える問題でも、シンプルな原則（貪欲法）を適用することで効率的に解決できる場合があること。もう一つは、変数を適切に管理（この場合は最低購入価格と最大利益）しながらデータを処理する思考法だ。これらのスキルは、株の売買に限らず、在庫管理システム、リソース配分、経路探索など、多岐にわたるシステム開発の現場で応用できる基礎的な考え方となる。システムエンジニアとして、このようなアルゴリズム的思考を身につけることは、より堅牢で高性能なソフトウェアを設計・開発するための第一歩となるだろう。