我在面试中遇到一道算法问题,但我似乎无法解决它。我知道应该如何进行,但无法以算法方式排序。
假设一家公司交易石油桶,并且每次只能保留一只油桶。假设公司知道一年中每天的每桶油的价格。所以将其作为数组传入。如何编写算法来确定何时购买和出售?
以下是简化为5天的示例:70 74 73 72 76
,分别为星期一到星期五的价格。
最好的方法是在星期一(70)购买,在星期二(74)出售,然后在星期四(72)购买,并在星期五(76)出售。是否可以采用递归方法?我真的想解决这个问题。
谢谢。
我在面试中遇到一道算法问题,但我似乎无法解决它。我知道应该如何进行,但无法以算法方式排序。
假设一家公司交易石油桶,并且每次只能保留一只油桶。假设公司知道一年中每天的每桶油的价格。所以将其作为数组传入。如何编写算法来确定何时购买和出售?
以下是简化为5天的示例:70 74 73 72 76
,分别为星期一到星期五的价格。
最好的方法是在星期一(70)购买,在星期二(74)出售,然后在星期四(72)购买,并在星期五(76)出售。是否可以采用递归方法?我真的想解决这个问题。
谢谢。
我猜你想要最大化你的利润,对吧?
那么,你只需要在本地最低点买入,在本地最高点卖出,这将是一个简单的线性搜索。
实际上,就是这么简单。证明如下:
我们用符号表示:
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))
,它将具有与上述相同的利润,这意味着它是最大化的。同时,这意味着您在局部最小值处购买,在局部最大值处出售。
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
在局部最高点卖出,在局部最低点买入。在开始前将价格视为无限大,在结束后将其视为零。
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。L[j] 表示第 j 天的利润。
L[j] = L[j-1] + MAX (0,Pj-Pj-1)
Pj 表示第 j 天的股票价格。
解决方案在于 L[n],因为每个 L[j] 给出了到那一点获得的最大利润,而 L[n] 给出了截至最后一天获得的最大利润。
运行时间:O(n)
(loop1)
(if currentPrice < nextPrice)
currentPrice = nextPrice
获取当前日期和下一个较低的售价之间的最高价格。
(loop2)
(if currentHighPrice<nextHighPrice)
currentHighPrice = nextHighPrice
else
sell(currentHighPriceDay)