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

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

admin2017-04-28  40
问题 设一个整形一维数组里有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=s um； if (sum＜0) //如果当前计算的子数组的和小于0，则将sum置0 sum=0； } printf("％d＼n"，max)； }
解析
转载请注明原文地址:https://kaotiyun.com/show/kWRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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