diff --git a/122/step1.md b/122/step1.md new file mode 100644 index 0000000..71188b9 --- /dev/null +++ b/122/step1.md @@ -0,0 +1,48 @@ +# step1 何も見ずに解く + +簡単な例で確認した。 +ある時点を考えると、一つ前の値段が安い時はその時に買って、ある時点で売れば良いだけであることに気づいた。 +時間計算量はO(N)で空間計算量はO(1) + +```ruby +# @param {Integer[]} prices +# @return {Integer} +def max_profit(prices) + prices_size = prices.size + return 0 if prices_size <= 1 + + max_profit = 0 + buy_price = prices.first + prices.each do |sell_price| + if sell_price > buy_price + max_profit += sell_price - buy_price + end + buy_price = sell_price + end + max_profit +end +``` + +もう少し見やすくできる。 + +```ruby +# @param {Integer[]} prices +# @return {Integer} +def max_profit(prices) + max_profit = 0 + prices.each_cons(2) do |prev_price, current_price| + next unless current_price > prev_price + max_profit += current_price - prev_price + end + max_profit +end +``` + +これもRubyっぽくてありかもしれない。 +```ruby +# @param {Integer[]} prices +# @return {Integer} +def max_profit(prices) + prices.each_cons(2).map { |prev_price, current_price| [0, current_price - prev_price].max }.inject(:+) || 0 +end +``` diff --git a/122/step2.md b/122/step2.md new file mode 100644 index 0000000..044921d --- /dev/null +++ b/122/step2.md @@ -0,0 +1,19 @@ +# step2 他の方の解答を見る +## 最小売買回数 +https://github.com/Yoshiki-Iwasa/Arai60/pull/53#discussion_r1730194725 + +up trendが終わったタイミングで売買を行えば良いので、以下のような感じで出せる。 + +```ruby +# @param {Integer[]} prices +# @return {Integer} +def min_trading_count(prices) + min_trading_count = 0 + is_up_trend = false + prices.each_cons(2) do |prev_price, current_price| + min_trading_count += 1 if is_up_trend && current_price < prev_price + is_up_trend = current_price > prev_price + end + min_trading_count +end +``` diff --git a/122/step3.md b/122/step3.md new file mode 100644 index 0000000..40bd939 --- /dev/null +++ b/122/step3.md @@ -0,0 +1,14 @@ +# step3 3回続けて10分以内に書いてエラーを出さなければOKとする + +```ruby +# @param {Integer[]} prices +# @return {Integer} +def max_profit(prices) + max_profit = 0 + prices.each_cons(2) do |prev_price, current_price| + next unless current_price > prev_price + max_profit += current_price - prev_price + end + max_profit +end +``` diff --git a/122/step4.md b/122/step4.md new file mode 100644 index 0000000..5941ee1 --- /dev/null +++ b/122/step4.md @@ -0,0 +1 @@ +## step4 レビューを受けて解答を修正