logo标签列表

面试问题：最大多次卖出利润

algorithm
17

我在面试中遇到一道算法问题，但我似乎无法解决它。我知道应该如何进行，但无法以算法方式排序。

假设一家公司交易石油桶，并且每次只能保留一只油桶。假设公司知道一年中每天的每桶油的价格。所以将其作为数组传入。如何编写算法来确定何时购买和出售？

以下是简化为5天的示例：70 74 73 72 76，分别为星期一到星期五的价格。

最好的方法是在星期一（70）购买，在星期二（74）出售，然后在星期四（72）购买，并在星期五（76）出售。是否可以采用递归方法？我真的想解决这个问题。

谢谢。

1
这是在任何投资公司面试中他们最常见和明显的问题。如果你不能回答这个问题，那么你没有做足研究和准备...请参阅上述内容。 - Suraj Chandran
@Suraj Chandran 我习惯于更多的数学/计算机科学问题。现在我正在尝试涉足更多与计算机科学/数学相关的金融问题。你是如何这么快地找到这些重复内容的？我在Stack Overflow上搜索了一段时间类似的问题。 - darksky
6
在我看来，那似乎不是一个重复问题，链接的那个问题只要求你找到一个买入/卖出。 - Mark B
1
@Suraj Chandran：如果我理解正确，这不是重复的问题。另一个问题想要最大化一笔交易，而这一个允许多笔交易。 - jpalecek
是的，您可以一次购买一个桶。 - darksky
显示剩余7条评论
6个回答
11

我猜你想要最大化你的利润，对吧？

那么，你只需要在本地最低点买入，在本地最高点卖出，这将是一个简单的线性搜索。

实际上，就是这么简单。证明如下：

我们用符号表示：

p(i) ... the price of oil on day i
have(i) ... 1 if we retain the barrel overnight from day i to day i+1, 0 otherwise

只有当 i 在 [0, N-1] 范围内时，have 才被定义。

现在，如果我们在第 k 天买入并在第 l 天卖出，我们会得到

have(k) = 1
have(l) = 0
have(i) = 1 for k < i < l

利润将会是

p(l)-p(k) = sum over {i from k to l-1} (p(i+1)-p(i))

让我们表示

M(i) = max(p(i+1) - p(i), 0)

对于所有可能的布尔函数have，我们有

profit(have) = sum over {i where have(i)==1} (p(i+1) - p(i))
 <= sum over {i where have(i)==1} max(p(i+1) - p(i), 0)
 <= sum over {i where have(i)==1} M(i)
 <= sum over {i in [0, N-1]} M(i)

第二行来自于 max(x, 0) >= x，第三行是简单的用 M(i) 重写，第四行来自于 M(i) >= 0。

现在，如果我们设置 have(i) == (p(i+1)>p(i))，它将具有与上述相同的利润，这意味着它是最大化的。同时，这意味着您在局部最小值处购买，在局部最大值处出售。

@nayefc - 你能解释一下这里的问题吗？我觉得这个回答是有效的。 - andrew cooke
1
我不明白你是如何找到局部最小值和最大值的。你能否提供一个算法在 OP 的例子上的样例运行？ - IVlad
这样的预知在所谓的交易策略中被允许吗？事后诸葛亮。 - Jimmy
1
如果第n+1天的价格比第n天高，那么你希望在第n天拥有一桶原油 - 否则不需要。如果你对某一天拥有一桶原油的愿望与前一天不同，那么你需要进行交易来解决这种情况。 - phkahler
@jpalecek： 好的，“sum over”是什么意思，为什么我们需要它？我理解到M(i)=max(p(i+1)-p(i),0)的部分。能否有人提供算法来获得利润(have)？ - Ronak Agrawal
2

O(N)时间复杂度和O(1)空间复杂度算法：

Starting at index 0
If you haven't bought an oil barrel:
    if price[i] < price[i + 1], buy at price[i]
    // if price[i] >= price[i + 1], you will never buy at price[i]
    // as price[i + 1] can bring you more money. So just wait...
If you have bought an oil barrel:
    if price[i] > price[i + 1], sell at price[i]
    // if price[i] <= price[i + 1], you will never sell at price[i]
    // as price[i + 1] can bring you more money. So just wait...

C++ 实现：

#include <iostream>
#include <vector>

int best_profit(const std::vector<int>& prices)
{
  bool buying = true;
  int buying_price = 0;
  int profit = 0;

  for(std::vector<int>::size_type i = 0; i < prices.size() - 1; ++i)
  {
    if(buying)
    {
      if(prices[i] < prices[i + 1])
      {
        buying_price = prices[i];
        buying = false;
      }
    }
    else if(prices[i] > prices[i + 1])
    {
      profit += prices[i] - buying_price;
      buying = true;
    }
  }

  if(!buying) // The last price is the highest one!
  {
    profit += prices[prices.size() - 1] - buying_price;
  }

  return profit;
}

int main()
{
  std::vector<int> prices1{1};
  std::vector<int> prices2{1, 2};
  std::vector<int> prices3{3, 2};
  std::vector<int> prices4{70, 74, 73, 72, 76};
  std::vector<int> prices5{70, 75, 71, 80, 96, 100, 15, 50, 60};

  std::cout << "prices1: " << best_profit(prices1) << std::endl;
  std::cout << "prices2: " << best_profit(prices2) << std::endl;
  std::cout << "prices3: " << best_profit(prices3) << std::endl;
  std::cout << "prices4: " << best_profit(prices4) << std::endl;
  std::cout << "prices5: " << best_profit(prices5) << std::endl;
}

输出：

prices1: 0
prices2: 1
prices3: 0
prices4: 8
prices5: 79
2

在局部最高点卖出，在局部最低点买入。在开始前将价格视为无限大，在结束后将其视为零。

1
从给定的价格中，我可以计算每日价格变动（即今天的价格-前一天的价格）。在这种情况下，“价格变化数组”将是[4，-1，-1，4]。
在“价格变动数组”中，正数表示价格已经上涨，负数表示价格已经下跌与前一天相比。
解决方案是找到“价格变化数组”中包含仅为正数的所有连续子数组。
使用这个思路，我编写了以下Python代码来打印买入和相应销售日的配对：
barrel_price = [70, 74, 73, 72, 76]
trading_days = {} #dictionary for storing {buy_day: sell_day}
buy_day=0
sell_day=buy_day+1

while sell_day < len(barrel_price):
    if barrel_price[sell_day]-barrel_price[sell_day-1]>0:
        #don't sell if price is still increasing
        sell_day=sell_day+1
        trading_days[buy_day] = sell_day-1
    else:
        #don't buy if price is still decreasing
        buy_day=sell_day
        sell_day=buy_day+1

print trading_days

这将打印出 "{0: 1, 3: 4}"。 对于第一对0:1，即购买日为0和销售日为1，相应的价格在barrel_price数组中为70和74。 对于下一对3:4，相应的购买价格为72，销售价格为76。
0

L[j] 表示第 j 天的利润。
L[j] = L[j-1] + MAX (0,Pj-Pj-1)
Pj 表示第 j 天的股票价格。
解决方案在于 L[n]，因为每个 L[j] 给出了到那一点获得的最大利润，而 L[n] 给出了截至最后一天获得的最大利润。
运行时间：O(n)

-1
只需比较价格： 每周搜索最低价格
(loop1)

(if currentPrice < nextPrice) 
currentPrice = nextPrice

获取当前日期和下一个较低的售价之间的最高价格。

(loop2)

(if currentHighPrice<nextHighPrice)
currentHighPrice = nextHighPrice
else
sell(currentHighPriceDay)
只需看一下楼主的示例就可以看出这个失败了。 - Jim Balter
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接