該問題給出了一個陣列，其中每個索引都是每天的股票價格：
array = [17,3,6,9,15,8,6,1,10]
例如，11 月 1 日的價格是 17 美元，11 月 2 日的價格是 3 美元，11 月 3 日的價格是 6 美元，等等。
我必須找到買賣的最佳日子，所以它應該回傳 [#{buy_day}, #{sell_day}]
在這種情況下，正確答案是 [1, 4]，利潤為 12 美元（以 3 美元買入，以 15 美元賣出）。為此，我使用了 reduce 方法并且它作業正常，但有人告訴我我沒有正確使用 reduce 方法。
stock = [17,3,6,9,15,8,6,1,10]
stocks_new = [17,3,6,9,15,8,6,1,10]
best_profit = 0
days = []
stock.length.times do |day|
stocks_new.reduce do |acc, val|
acc = stocks_new[0]
profit = val - acc
if profit > best_profit
best_profit = profit
days = [stock.index(acc), stock.index(val)]
end
end
stocks_new.shift
end
我首先將陣列復制到另一個變數 (stocks_new) 上，然后在每個回圈結束時移動。我這樣做是為了避免 |acc, val| 中的 val 從迭代中的累加器后面開始。
有沒有辦法將reduce方法中的val設定為每次迭代時從acc 1索引開始，這樣我就不必每次都創建這個stocks_new陣列并移位？
uj5u.com熱心網友回復：
不確定 reduce 方法問題，但也許您可以考慮一次性解決方案，不需要任何復制：
def max_profit(stock)
min_price = (1 << 31) - 1 # stock.max
max_profit = 0
min_day_index = 0
sell_day = 0
buy_day = 0
stock.each_with_index do |price, day_index|
if price < min_price
min_price = price
min_day_index = day_index
end
profit = price - min_price
if profit > max_profit
max_profit = profit
sell_day = day_index
buy_day = min_day_index
end
end
max_profit > 0 ? [buy_day, sell_day] : "Cannot make profit"
end
uj5u.com熱心網友回復：
正如@steenslag 在評論中所建議的，解決這個問題的直接方法是
(0..arr.size-1).to_a.combination(2).max_by { |i,j| arr[i]-arr[j] }
這需要 (n^2)/2 次計算，其中 n 是陣列的大小。
代碼
我將專注于一個更復雜的解決方案，我相信它可以大大減少更大陣列的求解時間。
def best_sell_buy(arr)
last_idx = arr.size-1
start_buy_idx = 1
sell_idx = 0
best = -Float::INFINITY
best_sell_buy = []
loop do
buy_idx = (start_buy_idx..last_idx).min_by { |i| arr[i] }
sell_idx =
if buy_idx == 1
0
else
[sell_idx, *start_buy_idx-1..buy_idx-1].max_by { |i| arr[i] }
end
cand = arr[sell_idx] - arr[buy_idx]
if cand > best
best = cand
best_sell_buy = [sell_idx, buy_idx]
end
break if buy_idx == last_idx
start_buy_idx = buy_idx 1
end
best_sell_buy
end
例子
arr = [17, 3, 6, 9, 15, 8, 6, 1, 10]
best_sell_buy(arr) # 2 iterations
#=> [0, 7]
arr[0]
#=> 17 (sell in period 0)
arr[7]
#=> 1 (buy in period 7)
prices = (100..300).to_a
#=> [100, 101, 102,..., 299, 300]
arr = 100.times.map { prices.sample }
#=> [254, 167, 182, 282, 119, 242, 181, 218, 269, 275,
# ... (80 elements)
# 255, 187, 205, 145, 189, 290, 254, 299, 224, 218] b
best_sell_buy(arr) # 4 iterations
#=> [31, 88]
arr[31]
#=> 299 (sell in period 31)
arr[88]
#=> 104 (buy in period 88)
arr = 100_000.times.map { prices.sample }
best_sell_buy(arr) # 468 iterations
#=> [110, 427]
arr[110]
#=> 300 (sell in period 110)
arr[427]
#=> 100 (buy in period 427)
我將在下一節解釋我所說的“迭代”是什么意思。
最后一個例子并不奇怪，因為從大小為 201 的總體中抽取了 100,000 個樣本，因此存在許多重復項。事實上，在前 428 個元素中找到了以最大值 (300) 賣出并以最小值 (100) 買入的解決方案，因此在此之后無法改進。
解釋
我將通過一個例子來解釋發生了什么：
arr = [5, 13, 6, 9, 1, 4, 17, 2, 10]
第一步是獲取最小值（買入）的指數：
i = arr.size.times.min_by { |i| arr[i] }
#=> 4 (arr[4] => 1)
接下來，我們獲得在此最小值（即 in arr[0..i-1] #=> arr[0..3]）之前的最大值（賣出）：
j = arr[0..3].max_by { |j| arr[j] }
#=> 1 (arr[1] => 13)
我們現在已經找到了陣列的最佳解決方案arr[0..4]，我們將其保存：
best_sell_buy = [1, 4]
best = arr[1] - arr[4] #=> 12
接下來，我們在剛找到的最小值的索引之后的陣列的剩余部分中找到最小值 ( arr[i 1..-1])：
i = arr[5..-1].min_by { |i| arr[i] }
#=> 7 (arr[7] => 2)
我們現在確定此買入期的最佳賣出期。以前我們已經考慮了 period 0..3，其中1最好。因此4..6，我們必須考慮周期以及我們之前在周期 1 中發現的最大值：
j = [1, *4..6].max_by { |i| arr[i] }
#=> 6 (arr[6] #=> 17)
銷售期6的17和期買7了2蚊帳15。由于這大于
best #=> 12
我們設定
best_sell_buy = [6, 7]
best = 15
我們現在有了陣列的最優解arr[0..7]。
最后，我們計算
i = arr[8..-1].min_by { |i| arr[i] }
#=> 8 (arr[8..-1] => [10])
和
j = [6, 7].max_by { |j| arr[j] }
#=> 6
作為
arr[6] - arr[8] = 17 - 10 = 7 < 15 (= best)
并i索引 的最后一個元素arr，我們得出最優解（對于arr）是[6, 7]。
如果我將每一i, j對的計算視為一次迭代，則此示例需要三個“迭代” 。我已經展示了解決每個早期示例所需的迭代次數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/391216.html