I'm trying to find the the best time to buy and sell these "stocks". For instance in array "f" buying on 3 and selling at 15 would = maximum_profit. I'm struggling to figure this out, starting to feel slightly dumb. I need to iterate through the array and find the best combo but once I pass a "day" I cant sell it on a day before that, only after.
我在寻找买卖这些“股票”的最佳时机。例如，在数组“f”中，购买3，在15时卖出，等于最大利润。我努力想弄明白，开始觉得有点傻。我需要遍历数组并找到最好的组合，但是一旦我过了“一天”，我就不能在前一天卖掉它，只有在那之后。
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)
2 个解决方案
#1
4
Here's a more Ruby way to solve the problem. The key here is to leverage tools like combination to do a lot of the heavy lifting for you, then transform that data step by step into the desired end result:
这里有一个更Ruby的方法来解决这个问题。这里的关键是利用组合这样的工具来为您完成大量繁重的工作，然后逐步将数据转换为所需的最终结果:
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
This gives you results like this:
结果如下:
{: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}
One of the important properties about combination is it preserves the order of the elements so this automatically excludes trades that would be impossible by happening in the wrong order.
组合的一个重要属性是它保留了元素的顺序，这样就自动排除了以错误的顺序发生的不可能的交易。
#2
2
My answer is an exercise to find an efficient way of solving the problem.
我的答案是找到解决问题的有效方法的练习。
Code
代码
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
This is for prices.size >= 2.
这是价格。大小> = 2。
Example
例子
prices = [17, 3, 6, 9, 15, 8, 6, 1, 10]
buy_sell(prices)
#=> [1, 4]
This means that the greatest profit can be made by buying at prices[1] #=> 3 on day (offset of prices) 1 and selling at prices[4] #=> 15 on day 4, for a profit of 12.
这意味着最大的利润可以通过在第一天以[1]#=> 3的价格买进(抵消价格)1，在第4天以[4]#=> 15的价格卖出，获得12的利润。
Explanation
解释
Consider the following array of daily prices.
考虑以下一系列的每日价格。
prices = [17, 3, 6, 9, 15]
17 is the price on day (offset) 0, 3 is the price on day 1, and so on.
17是第一天的价格(抵消)0,3是第一天的价格，以此类推。
We might first determine the index i > 0 of prices for which prices[i] is greatest.
我们可以先确定价格[i]最大的价格指数i >。
n = prices.size
#=> 5
imax = (1..n-1).max_by { |i| prices[i] }
#=> 4
Since imax #=> 4 we see that prices' largest value after the first day is on its last day, where prices[imax] #=> 15. That tells us that regardless of when we will buy, we should sell on the last day (proved easily by contradiction). It therefore remains to compute:
由于imax #=> 4，我们看到第一天之后价格的最大价值是在它的最后一天，价格[imax] #=> 15。这就告诉我们，无论何时买进，我们都应该在最后一天卖出(很容易被矛盾证明)。因此，仍需计算:
imin = (0..imax-1).min_by { |i| prices[i] }
#=> 1
We therefore should buy on day 1, at prices[1] #=> 3 and sell on day 4 at 15, giving us a tidy profit of 12.
因此，我们应该在第一天买进，以[1]#=> 3的价格，在第4天以15的价格卖出，这样我们就能获得12的可观利润。
Of course, the largest price after the first day is not necessarily on the last day. Now suppose:
当然，第一天之后的最大价格不一定是最后一天。现在假设:
prices = [17, 3, 6, 9, 15, 8, 6, 1, 10]
which is the OP's example. The calculation of the maximum price after the first day is now:
这是OP的例子。第一天后的最高价格计算为:
n = prices.size
#=> 9
imax = (1..n-1).max_by { |i| prices[i] }
#=> 4
15, on day 4 is still the highest price and we already know that before day 4, day 1 has the lowest price. This allows us to conclude the following: we should either buy on day 1 and sell on day 4, or we should buy after day 4 (and sell after that). Again, this is easily proved by contradiction, as selling anytime after day 4 will give us a sell price of at most 15, so we cannot have a larger profit than 12 by buying before day 4. The remaining problem is the array
第4天的价格仍然是最高的，我们已经知道在第4天之前，第一天的价格是最低的。这让我们得出以下结论:我们要么在第一天买进，然后在第4天卖出，要么在第4天之后买进(然后再卖出)。同样，这很容易被矛盾证明，因为4天以后的任何时候卖出都会给我们最多15的卖价，所以4天前买12是不能有比12更大的利润的。剩下的问题是数组
prices = [8, 6, 1, 10]
where 8 is the price on day 5, and so on.
第5天的价格是8，以此类推。
Since the largest sell price in this array is at the end, we know that the optimum is to buy at 1 on day 7 (offset 2 of the new prices) and sell on day 8 (offset 3), yielding a profit of 9. Since 9 < 12 we see that the highest profit is what we calculated initially.
由于这个数组的最大销售价格在最后，我们知道最优的是在第7天(新价格的抵销2)买1，然后在第8天卖出(抵消3)，收益9。因为9 < 12，我们看到最高的利润是我们最初计算出来的。
Had prices here been [1, 10, 8, 6] we would have computed the same profit of 9, but then had to consider prices being the array [8, 6]. Had prices here been [8, 1, 10, 6] we would have computed the same profit of 9, but then had to consider prices being the array [6], which we could disregard since it only contains single price.
如果这里的价格是[1,10,8,6]，我们就会计算出同样的利润为9，但是必须考虑价格是数组[8,6]。如果这里的价格是[8,1,10,6]，我们就会计算出同样的利润9，但是必须考虑价格是[6]数组，我们可以忽略它，因为它只包含一个价格。
This algorithm lends itself to a recursive implementation.
该算法适合递归实现。
Efficiency
效率
If there are m subarrays to consider, the time complexity is O(mn), compared to O(n2) for a straightforward comparison of all pairs [prices[i], prices[j]], i < j.
如果要考虑m个子数组，那么时间复杂度为O(mn)，与O(n2)相比，对所有对进行简单的比较[price [i]， prices[j]]]， i < j。
I have performed a benchmark to compare this approach with a simplified version of that used by @tadman, which enumerates all ordered pairs. The results are as follows.
我执行了一个基准来比较这种方法和@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| y-x }
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
reports the following.
以下报告。
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
Out of curiosity I computed the average number of recursions required for each value of n tested. The results are as follows.
出于好奇，我计算了每个被测试的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
When n equals 100, for example, on average, a sequence of 4.50 recursive calculations were required (i.e., each determining the maximum value of a subarray of prices and then determining the minimum value preceding the maximum). Not unexpectedly, that number increases slowly as n is increased.
当n = 100时，例如，平均来说，需要一个由4.50次递归计算组成的序列(即，每一个都确定价格子数组的最大值，然后确定在最大值之前的最小值)。不出意外的是，这个数字随着n的增加而缓慢增加。
#1
4
Here's a more Ruby way to solve the problem. The key here is to leverage tools like combination to do a lot of the heavy lifting for you, then transform that data step by step into the desired end result:
这里有一个更Ruby的方法来解决这个问题。这里的关键是利用组合这样的工具来为您完成大量繁重的工作，然后逐步将数据转换为所需的最终结果:
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
This gives you results like this:
结果如下:
{: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}
One of the important properties about combination is it preserves the order of the elements so this automatically excludes trades that would be impossible by happening in the wrong order.
组合的一个重要属性是它保留了元素的顺序，这样就自动排除了以错误的顺序发生的不可能的交易。
#2
2
My answer is an exercise to find an efficient way of solving the problem.
我的答案是找到解决问题的有效方法的练习。
Code
代码
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
This is for prices.size >= 2.
这是价格。大小> = 2。
Example
例子
prices = [17, 3, 6, 9, 15, 8, 6, 1, 10]
buy_sell(prices)
#=> [1, 4]
This means that the greatest profit can be made by buying at prices[1] #=> 3 on day (offset of prices) 1 and selling at prices[4] #=> 15 on day 4, for a profit of 12.
这意味着最大的利润可以通过在第一天以[1]#=> 3的价格买进(抵消价格)1，在第4天以[4]#=> 15的价格卖出，获得12的利润。
Explanation
解释
Consider the following array of daily prices.
考虑以下一系列的每日价格。
prices = [17, 3, 6, 9, 15]
17 is the price on day (offset) 0, 3 is the price on day 1, and so on.
17是第一天的价格(抵消)0,3是第一天的价格，以此类推。
We might first determine the index i > 0 of prices for which prices[i] is greatest.
我们可以先确定价格[i]最大的价格指数i >。
n = prices.size
#=> 5
imax = (1..n-1).max_by { |i| prices[i] }
#=> 4
Since imax #=> 4 we see that prices' largest value after the first day is on its last day, where prices[imax] #=> 15. That tells us that regardless of when we will buy, we should sell on the last day (proved easily by contradiction). It therefore remains to compute:
由于imax #=> 4，我们看到第一天之后价格的最大价值是在它的最后一天，价格[imax] #=> 15。这就告诉我们，无论何时买进，我们都应该在最后一天卖出(很容易被矛盾证明)。因此，仍需计算:
imin = (0..imax-1).min_by { |i| prices[i] }
#=> 1
We therefore should buy on day 1, at prices[1] #=> 3 and sell on day 4 at 15, giving us a tidy profit of 12.
因此，我们应该在第一天买进，以[1]#=> 3的价格，在第4天以15的价格卖出，这样我们就能获得12的可观利润。
Of course, the largest price after the first day is not necessarily on the last day. Now suppose:
当然，第一天之后的最大价格不一定是最后一天。现在假设:
prices = [17, 3, 6, 9, 15, 8, 6, 1, 10]
which is the OP's example. The calculation of the maximum price after the first day is now:
这是OP的例子。第一天后的最高价格计算为:
n = prices.size
#=> 9
imax = (1..n-1).max_by { |i| prices[i] }
#=> 4
15, on day 4 is still the highest price and we already know that before day 4, day 1 has the lowest price. This allows us to conclude the following: we should either buy on day 1 and sell on day 4, or we should buy after day 4 (and sell after that). Again, this is easily proved by contradiction, as selling anytime after day 4 will give us a sell price of at most 15, so we cannot have a larger profit than 12 by buying before day 4. The remaining problem is the array
第4天的价格仍然是最高的，我们已经知道在第4天之前，第一天的价格是最低的。这让我们得出以下结论:我们要么在第一天买进，然后在第4天卖出，要么在第4天之后买进(然后再卖出)。同样，这很容易被矛盾证明，因为4天以后的任何时候卖出都会给我们最多15的卖价，所以4天前买12是不能有比12更大的利润的。剩下的问题是数组
prices = [8, 6, 1, 10]
where 8 is the price on day 5, and so on.
第5天的价格是8，以此类推。
Since the largest sell price in this array is at the end, we know that the optimum is to buy at 1 on day 7 (offset 2 of the new prices) and sell on day 8 (offset 3), yielding a profit of 9. Since 9 < 12 we see that the highest profit is what we calculated initially.
由于这个数组的最大销售价格在最后，我们知道最优的是在第7天(新价格的抵销2)买1，然后在第8天卖出(抵消3)，收益9。因为9 < 12，我们看到最高的利润是我们最初计算出来的。
Had prices here been [1, 10, 8, 6] we would have computed the same profit of 9, but then had to consider prices being the array [8, 6]. Had prices here been [8, 1, 10, 6] we would have computed the same profit of 9, but then had to consider prices being the array [6], which we could disregard since it only contains single price.
如果这里的价格是[1,10,8,6]，我们就会计算出同样的利润为9，但是必须考虑价格是数组[8,6]。如果这里的价格是[8,1,10,6]，我们就会计算出同样的利润9，但是必须考虑价格是[6]数组，我们可以忽略它，因为它只包含一个价格。
This algorithm lends itself to a recursive implementation.
该算法适合递归实现。
Efficiency
效率
If there are m subarrays to consider, the time complexity is O(mn), compared to O(n2) for a straightforward comparison of all pairs [prices[i], prices[j]], i < j.
如果要考虑m个子数组，那么时间复杂度为O(mn)，与O(n2)相比，对所有对进行简单的比较[price [i]， prices[j]]]， i < j。
I have performed a benchmark to compare this approach with a simplified version of that used by @tadman, which enumerates all ordered pairs. The results are as follows.
我执行了一个基准来比较这种方法和@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| y-x }
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
reports the following.
以下报告。
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
Out of curiosity I computed the average number of recursions required for each value of n tested. The results are as follows.
出于好奇，我计算了每个被测试的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
When n equals 100, for example, on average, a sequence of 4.50 recursive calculations were required (i.e., each determining the maximum value of a subarray of prices and then determining the minimum value preceding the maximum). Not unexpectedly, that number increases slowly as n is increased.
当n = 100时，例如，平均来说，需要一个由4.50次递归计算组成的序列(即，每一个都确定价格子数组的最大值，然后确定在最大值之前的最小值)。不出意外的是，这个数字随着n的增加而缓慢增加。