概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
121. Best Time to Buy and Sell Stock
配列priceが与えられ、price[i]は指定された銘柄のi日目の価格である。
あなたは、ある銘柄を買うために1日を選び、その銘柄を売るために将来の異なる日を選ぶことによって、利益を最大化したいと思います。
この取引で達成できる最大の利益を返しなさい。もし利益が得られない場合は0を返せ。
制約
1 <= prices.length <= 1050 <= prices[i] <= 104
解説
時間コストO(n) 、空間コストO(1)となる解法です。
安い日に買って高い日に売る。一番利益が高いのはいつ買っていつ売ればよいかを考える問題です。
まずは[8,2,6,4,7,1,2,4,3]を例にしてグラフ化してみましょう。
このようなグラフとなりました。
今回は一回の購入で最大の利益出す問題ですので、『いつ買うか』と『いつ売るか』を探索していきます。
まずは購入日と売却日を表す変数を2つ用意しましょう。値は一番早い初日の１と二日目の2です。
var buyDate = 0;
var sellDate = 1;
次に一巡で探索を完了させるため、売却日が最後になるまでwhile文でループさせます。
そして購入日の値段と売却日の値段を比較し利益が出るか損となるかを判断します。
利益が出た場合は現時点での最高利益と比較して高い方を最高利益として値を更新します。
損になった場合は現時点の売却日を購入日に設定しさらに低い値段で購入し高い利益を出せるか試みます。
判定が完了したら売却日を次の日に進めて探索を再開します。
利益の場合は『別の日に売った方が高いかも』、損だった場合は『さらに安い日に買って利益を出した方が高いかも』という理由で売却日を翌日にずらしています。
最後に最大利益を返して終了です。
while (sellDay < prices.Length)
{
// 利益が出るならば
if (prices[buyDate] < prices[sellDate])
{
// この日売った場合の利益と最高利益を比較して高い方を最高利益とする
var profit = prices[sellDate] - prices[buyDate];
maxProfit = Math.Max(maxProfit, profit);
}
else
{
// さらに安い日に購入した場合で探索再開
buyDate = sellDate;
}
// 売却日を次の日に進める
sellDate++;
}
return maxProfit;スライドショー
ソースコード
public class Solution {
public int MaxProfit(int[] prices)
{
var buyDate = 0;
var sellDate = 1;
var maxProfit = 0;
while (sellDate < prices.Length)
{
// 利益が出るならば
if (prices[buyDate] < prices[sellDate])
{
// この日売った場合の利益と最高利益を比較して高い方を最高利益とする
var profit = prices[sellDate] - prices[buyDate];
maxProfit = Math.Max(maxProfit, profit);
}
else
{
// さらに安い日に購入した場合で探索再開
buyDate = sellDate;
}
// 売却日を次の日に進める
sellDate++;
}
return maxProfit;
}
}