最大化总利润

Question

假设汽车的价格每天都在波动，但在任何一天，价格总是一样的。假设一个人在价格低的时候买进，在价格高的时候卖出。

但每天只允许进行以下操作之一。

Buy one car.
Sale all cars that he owns
Do nothing

可以获得的最大金额是多少？

例如:假设我们有N(=3)天，并且每3天的车费是{1,3,70}，其中Ci代表ith day.Then的成本，在这种情况下可以得到的最大金额是136。

说明:他可以在头两天买一辆车，第三天可以把两辆车都卖掉。

如何找到最大金额？

Answer 1

让普利切克成为第一天的汽车价格#k

maxP = -inf
for k = last_day downto first_day 
  P = Price[k]
  if P < maxP then
    Action[k] = "Buy one car"
  else
    maxP = P
    Action[k] = "Sale all cars that he owns"
  end if
end for
carsOwned = 0
sumEarned = 0
for k = first_day to last_day
  P = Price[k]
  if Action[k] == "Buy one car" then
    carsOwned += 1
    sumEarned -= P
  else
    sumEarned += P*carsOwned
    carsOwned = 0
  end if
end for
print(sumEarned)

这个解决方案需要O(n)内存和O(n)时间。

Answer 2

让我们从显而易见的开始--如果你知道价格是最高的那一天(在你的一系列汽车价格中，每天的最大值的指数)，很明显，在那一天之前的最佳行动是每天买一辆车，然后在最大的一天把它们全部卖掉。

因此，解决这一问题的一个算法是找到最大值，在子数组0:index_of_max中计算每天购买一辆汽车并在最大程度上销售的利润，并对剩余的数组重申这一过程。时间复杂度为O(n^2)。