设有n个不全为负的整型元素存储在一维数组A[n]中,它包含很多连续的子数组,例如数组A={1,一2,3,10,一4,7,2,一5},请设计一个时间上尽可能高效的算法,求出数组A的子数组之和的最大值(例如数组A的最大的子数组为{3,10,一4,7,2},因此

admin2018-07-17  27

问题 设有n个不全为负的整型元素存储在一维数组A[n]中,它包含很多连续的子数组,例如数组A={1,一2,3,10,一4,7,2,一5},请设计一个时间上尽可能高效的算法,求出数组A的子数组之和的最大值(例如数组A的最大的子数组为{3,10,一4,7,2},因此输出为该子数组的和18)。要求:
    (1)给出算法的基本设计思想。
    (2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
    (3)说明你所设计算法的时间复杂度和空间复杂度。

选项

答案采用动态规划法。若记 [*] 则所求最大子段和为: [*] 由b[j]的定义可知,当b[j—1]>0时,b[j]=b[j—1]+a[j],否则b[j]=a[j]。 由此可计算b[j]的动态规划递归式:b[j]=max{b[j—1]+a[j],a[j]),1≤j≤n,据此,可设计出求最大字段和的算法如下: 算法思想如下: 不妨对数组元素进行一次遍历,下面是选取一个元素加入子段的一般方法: 倘若一个子段和为b,那么判断下个元素a[k+1]的标准应该为b+a[k+1]≥0(因为当b<0时,任意一

解析
转载请注明原文地址:https://kaotiyun.com/show/F8Ri777K
0

最新回复(0)