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

admin2017-11-20  29

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

选项

答案时间复杂分析:整个算法过程相当于把数组遍历了一遍,所以时间复杂度为O(n)。 空间复杂度分析:算法中只需要使用sum和max这两个临时变量,所以空间复杂度为一常数,表示为O(1)。

解析
转载请注明原文地址:https://jikaoti.com/ti/QEfjFFFM
0

最新回复(0)