需要帮助操作ruby中的数组
我正试图找到买卖这些“股票”的最佳时机。 例如，数组“f”在3买入并在15卖出= = maximum_profit。 我正在努力解决这个问题，开始感到有些愚蠢。 我需要遍历数组并找到最好的组合，但是一旦我过了一天，我就不能在那之前的一天卖掉它，只有在之后。
a = [1, 2, 3, 4, 5, 6, 7, 8, 9] b = [9, 8, 7, 6, 5, 4, 3, 2, 1] c = [3, 4, 2, 6, 7, 4, 9, 8, 5] d = [8, 6, 9, 2, 7, 4, 1, 5 ,1] e = [10, 11, 2, 9, 4, 3, 5, 6] f = [17, 3, 6, 9, 15, 8, 6, 1, 10] def stock_picker(array) min = array.min min_price= array.index(min) max = array.max max_price = array.index(max) end stock_picker(a) 这是解决问题的更多Ruby方法。 这里的关键是利用combination工具为您完成大量繁重工作，然后逐步将数据转换为所需的最终结果：
def max_profit(prices) best = prices.combination(2).map do |buy, sell| [ buy, sell, sell - buy ] end.max_by do |buy, sell, profit| profit end if (best[2] <= 0) { profit: 0 } else { buy: { at: best[0], on: prices.index(best[0]) }, sell: { at: best[1], on: prices.index(best[1]) }, profit: best[2] } end end stocks = [ [1, 2, 3, 4, 5, 6, 7, 8, 9], [9, 8, 7, 6, 5, 4, 3, 2, 1], [3, 4, 2, 6, 7, 4, 9, 8, 5], [8, 6, 9, 2, 7, 4, 1, 5 ,1], [10, 11, 2, 9, 4, 3, 5, 6], [17, 3, 6, 9, 15, 8, 6, 1, 10] ] stocks.each do |prices| p max_profit(prices) end
这给你这样的结果：
{:buy=>{:at=>1, :on=>0}, :sell=>{:at=>9, :on=>8}, :profit=>8} {:profit=>0} {:buy=>{:at=>2, :on=>2}, :sell=>{:at=>9, :on=>6}, :profit=>7} {:buy=>{:at=>2, :on=>3}, :sell=>{:at=>7, :on=>4}, :profit=>5} {:buy=>{:at=>2, :on=>2}, :sell=>{:at=>9, :on=>3}, :profit=>7} {:buy=>{:at=>3, :on=>1}, :sell=>{:at=>15, :on=>4}, :profit=>12}
关于combination一个重要特性是它保留了元素的顺序，因此这自动排除了以错误的顺序发生的交易。
我的答案是找到解决问题的有效方法。
码
def buy_sell(prices) n = prices.size imax = (1..n-1).max_by { |i| prices[i] } imin = (0..imax-1).min_by { |i| prices[i] } return [imin, imax] if imax >= n-2 imin_next, imax_next = buy_sell(prices[imax+1..-1]).map { |i| i + imax } prices[imin]-prices[imax] >= prices[imin_next]-prices[imax_next] ? [imin, imax] : [imin, imax] end
这适用于prices.size >= 2 。
例
prices = [17, 3, 6, 9, 15, 8, 6, 1, 10] buy_sell(prices) #=> [1, 4]
这意味着最大的利润可以通过以当天的prices[1] #=> 3购买（ prices[1] #=> 3抵消） 1并在第4天以prices[4] #=> 15出售，获利12 。
说明
考虑以下每日价格数组。
prices = [17, 3, 6, 9, 15]
17是当天的价格（抵消） 0是第1天的价格，依此类推。
我们可能首先确定prices[i]最大的prices的指数i > 0 。
n = prices.size #=> 5 imax = (1..n-1).max_by { |i| prices[i] } #=> 4
由于imax #=> 4我们看到prices在第一天之后的最大值是在最后一天，其中prices[imax] #=> 15 。 这告诉我们，不管我们什么时候买，我们应该在最后一天卖出（很容易被矛盾certificate）。 因此，仍需计算：
imin = (0..imax-1).min_by { |i| prices[i] } #=> 1
因此，我们应该在第1天以prices[1] #=> 3购买，并在第4天以15 prices[1] #=> 3出售，从而获得12美元的整洁利润。
当然，第一天之后的最大价格不一定是最后一天。 现在假设：
prices = [17, 3, 6, 9, 15, 8, 6, 1, 10]
这是OP的例子。 现在计算第一天后的最高价格：
n = prices.size #=> 9 imax = (1..n-1).max_by { |i| prices[i] } #=> 4
15 ，第4天仍然是最高价格，我们已经知道在第4天之前，第1天的价格最低。 这使我们得出以下结论：我们应该在第1天购买并在第4天出售，或者我们应该在第4天之后购买（并在之后出售）。 同样，这很容易通过矛盾certificate，因为第4天之后的任何时间卖出将给我们最多15的卖出价，因此我们在第4天之前购买的利润不会超过12 。 剩下的问题是数组
prices = [8, 6, 1, 10]
其中8是第5天的价格，依此类推。
由于该arrays中最大的卖出价格最终，我们知道最优的是在第7天买入1 （新prices抵消2 ）并在第8天卖出（抵消3 ），获利9 。 从9 < 12我们看到最高利润是我们最初计算的。
如果这里的prices是[1, 10, 8, 6] 1,10,8,6 [1, 10, 8, 6]我们会计算9的相同利润，但后来不得不考虑prices是数组[8, 6] 。 如果这里的prices是[8, 1, 10, 6]我们会计算9的相同利润，但后来不得不考虑prices是arrays[6] ，我们可以忽略它，因为它只包含单一价格。
该算法适用于递归实现。
效率
如果要考虑m个子arrays，则时间复杂度为O（mn），与O（n 2 ）相比，所有对[prices[i], prices[j]] ， i < j的直接比较。
我已经执行了一个基准测试，将这种方法与@tadman使用的简化版本进行比较，后者列举了所有有序对。 结果如下。
def cary_buy_sell(prices) n = prices.size imax = (1..n-1).max_by { |i| prices[i] } imin = (0..imax-1).min_by { |i| prices[i] } return [imin, imax] if imax >= n-2 imin_next, imax_next = cary_buy_sell(prices[imax+1..-1]).map { |i| i + imax } prices[imin]-prices[imax] >= prices[imin_next]-prices[imax_next] ? [imin, imax] : [imin, imax] end def tadman_buy_sell(prices) prices.combination(2).max_by { |x,y| yx } end require 'fruity' m = 20 [10, 20, 100, 1000].each do |n| puts "\nn = #{n}, m = #{m}" prices = m.times.map { n.times.to_a.shuffle } compare do tadman { prices.each { |row| tadman_buy_sell(row) } } cary { prices.each { |row| cary_buy_sell(row) } } end end
报告以下内容。
n = 10, m = 20 Running each test 16 times. Test will take about 1 second. cary is faster than tadman by 1.9x ± 0.1 n = 20, m = 20 Running each test 8 times. Test will take about 1 second. cary is faster than tadman by 4x ± 0.1 n = 100, m = 20 Running each test once. Test will take about 1 second. cary is faster than tadman by 22x ± 1.0 n = 1000, m = 20 Running each test once. Test will take about 28 seconds. cary is faster than tadman by 262x ± 10.0
出于好奇，我计算了n测试值的平均递归次数。 结果如下。
average number of n recursions required --------------------------- 10 2.40 20 2.55 100 4.50 1,000 6.65 10,000 8.55 50,000 9.85 100,000 11.60 500,000 13.40
例如，当n等于100 ，平均而言，需要4.50递归计算的序列（即，每个确定价格子arrays的最大值，然后确定最大值之前的最小值）。 出乎意料的是，随着n的增加，这个数字会缓慢增加。