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

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

admin2018-07-17  59
问题 设有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
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)