设一个整形一维数组里有n(n>1)个整数,在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法,输出所有子数组的和的最大值。例如一维数组中的整数为1,-2,3,10,

admin2017-11-20  34

问题 设一个整形一维数组里有n(n>1)个整数,在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法,输出所有子数组的和的最大值。例如一维数组中的整数为1,-2,3,10,-4,7,2,-5,则和最大的子数组为3,10,-4,7,2,该子数组的和为18。要求:
给出算法的基本设计思想。

选项

答案算法的策略是遍历数组,用事先定义好的求和变量(初始化为0)加上当前元素后得到一个新的和,先判断这个和是否比前面已经记录的最大字数组和大,如果大,则更新此记录。然后再判断这个和是否为负数,如果是个负数,那么这个和应该被重新置0,否则这个负数将会减少接下来的和。

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

最新回复(0)