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

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

admin2017-11-20  48
问题 设一个整形一维数组里有n(n＞1)个整数，在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法，输出所有子数组的和的最大值。例如一维数组中的整数为1，-2，3，10，-4，7，2，-5，则和最大的子数组为3，10，-4，7，2，该子数组的和为18。要求：
根据设计思想，采用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)； }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/SNRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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