こちらは「Best Time To Buy And Sell Stock」のPythonによる解答例となっております。この問題は、整数の配列が与えられたときに、その配列内の要素を購入して販売することで得られる最大の利益を求める問題です。
問題
整数の配列 prices が与えられたとき、この配列内の要素を購入して販売することで得られる最大の利益を求めます。ただし、購入価格は販売価格よりも前でなければなりません。
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
解法
この問題は、配列内の要素を1つずつ処理し、それまでの最小値との差を計算して最大利益を求める方法があります。このアプローチの計算量は O(n) です。
アルゴリズムの概要を以下に述べます。
- 配列の最初の要素を現在の最小値
min_price
として初期化します。 - 配列を1つずつ反復処理します。
- 現在の要素と
min_price
の差を計算し、最大利益max_profit
と比較します。 - 現在の要素と
min_price
を比較し、より小さい方をmin_price
として更新します。 - 反復処理が終了したら、最大利益を返します。