c++之股票低买高卖问题

Question

题目描述
你有预测股票的能力：可以知道某只股票未来 N 天的价格。

你当然准备通过这项能力获利，但为了不让别人发现你的“钞能力”，只打算每天最多交易一股股票。也就是说，每天你要么买入一股，要么卖出一股（当你没有任何股票时，你就不能出售），要么什么都不做。

最初你拥有零股，但可以融资（借钱）。在 N 天结束后，你要把借来的钱还回去，同时帐下恢复零股。

现在问题来了：通过最合理的买卖，你可以从这 N 天内赚到多少钱。

输入格式
第一行输入一个数，表示 N。
接下来一行是 N 个数，
pi表示股票在第n天的价格

输出格式
输出一个数 M，表示这 N 天最多可以赚到的利润。

输入输出样例：

输入1：

9
10 5 4 7 9 12 6 2 10

输出1：

20

Answer 1

这是一个经典的股票买卖问题，可以使用贪心算法来解决。

具体思路是，在每个价格上升的阶段买入，在价格下降的阶段卖出，即对于第i天，如果pi>pi−1，则将第i−1天买入，第i天卖出，否则不进行操作。最终累加所得到的利润即可。