事实上，这个问题可以用最大子数组来解决，把某一天的股票价格减去前一天的股票价格，求出当天股票价格浮动变化，再加入到数组里，依次类推把每一天的价格浮动变化组合起来构成一个数组，求出它的最大子数组即为最大收益。
如何求出一个最大子数组(最大子数组可能有多个，求出一个即可)呢？
首先我们可以对这个数组进行分割，从中间划开一刀(如果数组元素个素为单数，偏左偏右划都是可以的)，那么这个最大子数组必然在这一刀的左边，右边或者跨越了这一刀痕的中间。
OK，那么接下来我们需要求出这三种情况的最大子数组，对它们三个进行比较，那么如何求出左边数组的最大子数组呢？聪明的人已经发现还是和刚才的求法一样，在左边的数组的中间再划一刀！是的，所以这个算法是用递归来实现的，一刀一刀划下去，最后会变成最简单的子问题，得到子问题的答案，再一级一级往回返，进行比较，就可以得出最终问题的解了。
接下来直接贴算法
附上项目下载地址:https://github.com/zizhouwang/GetMaxSubarray
以上所有文字图片均摘于算法导论原书第3版中文完整版 高清扫描版
网友评论