可获得的最大利润-买卖 [英] Maximum profit that can be obtained - Buying and Selling

问题描述

说，我们可以准确预测 N 天的梅西价格。预测以列表形式给出，其中 p_i 表示玩家在一天 i 中的价格。鲍勃计划在此期间进行多次连续交易，但一次不能拥有多个梅西，因此需要在再次购买之前卖掉他。

Say we have an accurate prediction of Messi’s prices for a period of N days. The prediction is given as a list in which p_i represents the player’s price in day i. Bob plans to make multiple, successive transactions during this period, but CAN’T have more than one Messi at a time, and therefore needs to sell him before buying him again.

鲍勃（Bob）最初的预算是 B ，他无法购买价格超出其承受能力的梅西。当然，鲍勃可以通​​过买卖Messis获得的任何利润增加预算。对他来说幸运的是，有时候他会从梅西开始，先是打开一个随机的礼物包。

Bob starts out with a limited budget B and can’t buy a Messi which costs more than he can afford. Of course, Bob can add to his budget any profit he gets from buying and selling his Messis. Luckily for him, some of the times he starts with a Messi from opening a random gift pack beforehand.

最后，鲍勃只是想尽可能多地赚钱，并出售最近的梅西历史记录。

At the end Bob just wants to have as much profit as possible, and sell hist last Messi.

输入格式：

在输入文件的第一行，您将找到3个整数N，B和M。

On the first line of the input file, you will find 3 integers, N, B and M.

N代表Bob预测了Messi的价格。
B代表鲍勃的初始预算。
M可以为0或1；如果鲍勃开始时没有初始梅西出售，则为0；如果鲍勃开始时没有初始梅西出售，则为1。

N represents the number of days for which Bob has a prediction of Messi’s price. B represents Bob’s initial budget. M can be either 0 or 1; 0 if Bob starts without an initial Messi to sell and 1 if he does start with an initial Messi to sell.

在下一行中，您会找到N个整数：p1， p2，…，pN，用空格隔开，其中pi表示梅西在第i天的价格。

On the next line you will find N integers: p1, p2, … , pN, separated by a whitespace, in which pi, represents Messi’s price on day i.

给出测试用例

测试1

7 5 0

20 10 30 5 10 10 20

20 10 30 5 10 10 20

正确答案：15

说明：Bob的初始预算为5，没有初始梅西可以出售。在价格跌至5之前，他无法购买任何梅西，因此他的利润仅为（20-5）= 15

Explanation : Bob starts with an initial budget of 5 and no initial Messi to sell. He cannot buy any Messi until his price drops to 5, so his profit is only (20-5) = 15

测试2

7 0 1

20 10 50 80 60 20 10

20 10 50 80 60 20 10

正确答案：90

说明：
Bob开头为初始预算为0，有一个梅西可以出售。因此，他以20的价格出售了最初的梅西，以10的价格买回了他，然后以80的价格卖给了他，因此他的利润为20 +（80-10）= 90

Explanation: Bob starts with an initial budget of 0 and one Messi to sell. Therefore he sells his initial Messi for 20, buys him back for 10 and sells him for 80, so his profit is 20 + (80-10) = 90

这个问题是在一次采访中给我的，但我还无法提供一个可行的解决方案。同时，我在此问题上发现了一些更简单的变体，例如通过最多买卖两次股份来获得最大利润，但我一直未能理解如何使思想适应我的问题。

This problem was given to me in an interview and I haven't been able to produce a functioning solution. In the meantime I've found a few simpler variations on this problem such as Maximum profit by buying and selling a share at most twice , but I've been unsuccessful in understanding how to adapt the thinking to my problem.

到目前为止，我只能提出一种蛮力解决方案，它远远超出了我给定的时间限制（C ++为0.1秒，其中1< = N< = 10 ^ 5）。

So far I've only been able to come up with a brute force solution that goes way beyond the time restrictions I was given (0.1 seconds for C++, where 1 <= N <= 10^5).

我正在寻找解决方案和思考此类问题的方法，但我似乎找不到正确的思考方式。

I'm looking for a solution and a way of thinking about this kind of problem, I can't seem to find the right way to think about this.

推荐答案

我们可以使用动态编程。

We can use dynamic programming.

1. 我们将 f0（i）定义为如果我们在一天之初没有梅西时获得的最大预算 i 。
   让 f1（i）等于我们要得到他的值。

1. Let's define f0(i) as the maximum budget we can obtain if we don't have Messi at the beginning of the day i. Let f1(i) be the same value in case we've got him.

i = 0 的基本值取决于我们是否一开始就拥有他。

Base values for i = 0 depend on whether we have him at the very beginning or not.

转换如下：

• 我们可以从 i 到 i + 1 而什么也不做

如果我们有梅西，我们可以卖掉他（设置 f0（i +1）= max（f0（i +1），f1（i）+ price（i）））

If we have Messi, we can sell him (setting f0(i + 1) = max(f0(i + 1), f1(i) + price(i)))

如果我们没有他并且我们的预算足够大，我们可以给他买
（做 f1（i + 1）= max（f1（i + 1），f0（i）-price（i）））

If we don't have him and our budget is big enough, we can buy him (doing f1(i + 1) = max(f1(i + 1), f0(i) - price(i)))

答案是 f0（n）（这意味着整天过去了，我们没有他）。

The answer is f0(n) (which mean that all days passed and we don't have him).

此解决方案显然需要线性的时间和空间，因此任何
合理的C ++实现都应符合您的要求。

This solution clearly requires a linear amount of time and space, so any reasonable C++ implementation should fit your requirements.

这篇关于可获得的最大利润-买卖的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！