问题描述
算法导论P38提到
来源:已知一股票在某一段时间内的变化趋势,问该时间段内何时买入,何时卖出,使得收益最大,求出最大值
转化:给定一个数组,从中选取一个连续的子数组,使得其元素和在所有的子数组中最大,返回该最大值。
解决方案
暴力搜索
n个元素中选取两个元素,计算两个元素之间的元素的和,将其与max相比,如果比max大,则替换;
代码如下:
分治策略
把一个数组从中分开为两个子数组,最大子数组可能的情况是:在左边的子数组,在右边的子数组,含左边的一部分和右边的一部分;对于前两种情况只是将原问题分解为较小的原问题,而第三种情况既然包括左边和右边,一定含有中间的元素,因此很好解决,从左从右遍历即可;然后将这三种情况进行比较,选取最大的部分返回
这个问题和归并排序是一个道理
DP解法
第sum[i-1]个元素是前i-1个元素的最大子数组的和,如果sum[i-1]小于0,则sum[i]=a[i],否则sum[i]=sum[i-1]+a[i];最后的结果result取sum[i]的最大值
sum[i]=max(a[i],sum[i-1]+a[i])
result=max(result,sum[i])