CF：391F1StockTrading动规DP

This problem consists of three subproblems: for solving subproblem F1 you will receive 8 points, for solving subproblem F2 you will receive 15 points, and for solving subproblem F3 you will receive 10
points.

Manao has developed a model to predict the stock price of a company over the next n days and wants to design a profit-maximizing trading algorithm to make
use of these predictions. Unfortunately, Manao‘s trading account has the following restrictions:

• 
  It only allows owning either zero or one shares of stock at a time;
• 
  It only allows buying or selling a share of this stock once per day;
• 
  It allows a maximum of k buy orders over the next n days;

For the purposes of this problem, we define a trade to a be the act of buying one share of stock on day i,
then holding the stock until some day j?>?i at which point the share is sold. To restate the above constraints, Manao is permitted to make at most k non-overlapping
trades during the course of an n-day trading period for which Manao‘s model has predictions about the stock price.

Even though these restrictions limit the amount of profit Manao can make compared to what would be achievable with an unlimited number of trades or the ability to hold more than one share at a time, Manao still has the potential to make a lot of money because
Manao‘s model perfectly predicts the daily price of the stock. For example, using this model, Manao could wait until the price is low, then buy one share and hold until the price reaches a high value, then sell for a profit, and repeat this process up to k times
until n days have passed.

Nevertheless, Manao is not satisfied by having a merely good trading algorithm, and wants to develop an optimal strategy for trading subject to these constraints. Help Manao achieve this goal by writing a program that will determine when to buy and sell stock
to achieve the greatest possible profit during the n-day trading period subject to the above constraints.