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

问答题给出算法的基本设计思想。

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

【答案解析】

问答题根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

【正确答案】正确答案：算法实现如下： void FindGreatestSumOfSubArray(int a[]，n) { int sum；／／sum用来记录子数组的和 int max；／／max用来记录最大子数组的和 int i； max=a[0]；／／将max的值初始化为数组中的第一个元素的值 sum=0，／／将sum的值初始化为0 for(i=0；i＜n；i++) { sum+=a[i]；／／计算子数组的和 if(sum＞max) ／／如果当前计算的子数组的和比之前记录的最大子数组的和大的话，则更新max的值 max=sum； if(sum＜0) ／／如果当前计算的子数组的和小于0，则将sum置0 sum=0； } printf(''％d＼n''，max)； }

【答案解析】

问答题说明所设计算法的时间复杂度和空间复杂度。

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

【答案解析】