股票每天会有涨跌，需要经过多次买进、抛售，实现股票收益最大化。假设把某股票的价格 按照时间先后顺序存储在数组中，求出可以获得的最大利润（对股票的买卖操作可以进行多次）。

本实战技能是Pyhton面试题中的常见问题，也是经典的动态规划问题—实现股票收益最大 化。运行程序得到的结果如下图所示。

 

股票收益最大化结果展示

 

【技术要点】

本实战技能的重点在于动态规划，动态规划是求解决策过程最优化的方法。将待求解的问题 分解成若干个子问题，按照顺序求解，前一个子问题的解为后一个子问题的解提供有用的信息。在 求解任一子问题时，列出局部解，通过决策保留可能达到最优解的局部解，丢弃其他局部解。依次解决各个子问题，最后一个子问题的解就是初始问题的解。

 

高手点拨：

适合于用动态规划的问题，经过分解之后得到的子问题往往不是相互独立的（即：下一个子阶段的求解是建立在上一个问题的基础上进行进一步的求解）。

这里举一个例子：假设你正在爬楼梯。需要 n 阶才能到达楼顶，每次可以爬1或2个台阶。有多少种不同的方法可以爬到楼顶呢？

（1）动态规划步骤1：假如我们是从第n-1级，跨1级上来，到第n级，或我们是从第n-2级，跨2级上来，到第n级，所以我们就得到了所谓的状态转移方程：F(n)=F(n-1)+F(n-2)，F(n-1) = F(n-2) + F(n-3)，F(n-2) = F(n-3) + F(n-4)，依此类推一直到最底层，当只有1级台阶时，F(1) = 1；当只有2级台阶时F(2) = 2。

（2）动态规划步骤2：自底向下构造。F(1)=1和F(2)=2，所以F(3) = F(2) + F(1) = 3，进一步地，F(4) = F(3) + F(2) = 5等。进而解决这个问题。

 

【主体设计】

股票收益最大化实现流程如下图所示。

 

股票最大增益实现流程图

 

股票收益最大化的实现步骤如下。

Step1：获得多次交易的股票价格。

Step2：计算相邻两天的股票差价。

Step3：得到差价收益，计算出股票的最大收益。

Step4：输出计算结果。

 

【编程实现】

本实战技能使用PyCharm工具进行编写，建立相关的源文件【股票收益最大化.py】，在界面输入代码。参考下面的详细步骤，编写具体代码，具体步骤及代码如下所示。

Step1：定义BestStock_n_time( )函数，基于动态规划的思想，实现股票价格差值，代码如下所示。

1. def BestStock_n_time(arr):

2. len1 = len(arr)

3. if len1 < 2:

4. return 0

5. diffArr = [] # 股票价格差值

6. add_value = []

7. for i in range(len1 - 1):

8. diffArr.append(arr[i + 1] - arr[i])

9. sum = 0 # 股票最大收益

10. for i in range(len(diffArr)):

11. if diffArr[i] > 0:

12. add_value.append(diffArr[i])

13. sum += diffArr[i]

14. return diffArr, add_value, sum

Step2：调用input( )函数，获得股票价格。调用BestStock_n_time( )函数，计算出股票最大收益，输出结果，代码如下所示。

1. if _name_ == '_main_':

2. print(" 股票收益最大化案例 ")

3. try:

4. while True:

5. print(" 股票价格：", end='')

6. arr = [int(i) for i in input( ).split( )]

7. diffArr, add_value, sum = BestStock_n_time(arr)

8. print(" 股票价格差值：", diffArr)

9. print(" 股票增值数：", add_value)

10. print(" 股票最大收益：{0}".format(sum))

11. except:

12. pass