概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
122. Best Time to Buy and Sell Stock II
整数配列priceが与えられ、price[i]は指定された銘柄のi日目の価格です。
毎日購入・売却ができますが、あなたは常に最大で1株しかその株式を保有できません。ただし、買った後すぐに売ることもできます。
あなたが達成できる最大の利益を見つけて返してください。
制約
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
関連問題
『121. Best Time to Buy and Sell Stock』を拡張した問題です。
まだ上記の問題を解答していない方はこちらから進めることをお勧めいたします。
また、以下のリンクで解説を行っていますので、解いた後に自分の解答と比較することをお勧めいたします。
C#で解くLeetCode「121. Best Time to Buy and Sell Stock」
解説
まずは前回の問題と比べてどこに差があるかを探しましょう。
今回の問題で変わっているのは何度も購入できる点です。
ただし、1株しか持てないので保有している状態でさらに買うことはできません。
最大利益を求めるにはどのように取引を行えばいいかを考えましょう。
最大利益を出すには利益が出る場合に株を保有しておき、損が出る場合に株を保有していないことを全ての日で実現することです。
まずは[8,2,3,6,5,2,1,4,3]を例にグラフにしてみましょう。
まずは上記の例で毎日どのように判断するかを考えます。
- 初日に購入すると翌日の株価が下がることで損が出てしまい最大利益を出せないので買いません
- 2日目に購入した場合は翌日の株価は上がり利益になるので購入します。
- 3日目は株を保有している状態なので売却を検討しますが、翌日も株価は上がるので保有し続けます。
- 4日目も株を保有しているので売却を検討します。翌日の株価は下がってしまうので損が出る前に売却をします。
つまり、購入日は検討日の翌日に利益が出始める直前となります。
売却日は購入日から検討を始め、検討日の翌日に損が出始める直前となります。
この流れを一巡で終わらせられるようにコードに表していきましょう。
まずは使用する変数を用意していきます。
// 検討日、合計利益、株価推移日数
var currentDate = 0;
var profit = 0;
var days = prices.Length - 1;次にすべての日にちで検討を行うため、ループを追加します。
最初に購入日を検討しますが、株価が上がる直前の日を購入日とします。
購入日が決まるまでは購入も売却も行わないので検討日をそのまま加算して進めましょう。
購入日が決まりましたら、利益を出すために計算をするので購入価格を記録しておきましょう。
while (currentDate < days)
{
// 株価が上がる直前の日を購入日とする
while (currentDate < days && prices[currentDate + 1] <= prices[currentDate])
{
currentDate++;
}
var buyPrice = prices[currentDate];
}次は売却日の検討です。
先ほどの購入日から検討を続け、検討日の翌日に損が出るまで同じ流れで売却日を確定させます。
売却日が確定したら得た利益を加算して、再度購入の検討にもどります。
最後に利益を返して終了です。
while (currentDate < days)
{
// 株価が上がる直前の日を購入日とする
while (currentDate < days && prices[currentDate + 1] <= prices[currentDate])
{
currentDate++;
}
var buyPrice = prices[currentDate];
// 購入日から次に株価が下がる直前の日を売却日とする
while (currentDate < days && prices[currentDate + 1] > prices[currentDate])
{
currentDate++;
}
var sellPrice = prices[currentDate];
// 売却して得た利益を加算する
profit += sellPrice - buyPrice;
}
return profit;ソースコード
public class Solution {
public int MaxProfit(int[] prices)
{
var currentDate = 0;
var profit = 0;
var days = prices.Length - 1;
while (currentDate < days)
{
// 株価が上がる直前の日を購入日とする
while (currentDate < days && prices[currentDate + 1] <= prices[currentDate])
{
currentDate++;
}
var buyPrice = prices[currentDate];
// 購入日から次に株価が下がる直前の日を売却日とする
while (currentDate < days && prices[currentDate + 1] > prices[currentDate])
{
currentDate++;
}
var sellPrice = prices[currentDate];
// 売却して得た利益を加算する
profit += sellPrice - buyPrice;
}
return profit;
}
}