3,输入一个整型数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如:输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18。
解题思路:当我们加上一个正数时,和会增加;当我们加上一个负数时,和会减少。如果当前得到的和是个负数,那么这个和在接下来的累加中应该抛弃并重新清零,不然的话这个负数将会减少接下来的和。
程序源码:
#include <iostream.h>
int get_sub_sum_max(int *arr, int len)
{
int max, sum;
max = arr[0]; //存储最大子数组 和
sum = 0; //判断 一直相加后 是否为负数 从而影响后面再相加
while (len--)
{
sum += *arr++; //下一个数组 元素 遇到负数 则清零
if (sum >=max)//当加上一个负数时 max 没有改变 观察后面加许多值后有木有 大于 max的
max = sum; //max存储sum 不是零的数后 ,再与下一轮 sum+arr[i] 后相比
else if (sum < 0) //当前的和为负数,则影响下一个数
sum = 0;
}
return max;
}
int main()
{
// int a[10]={1,-8,6,3,-1,5,7,-2,0,1}; //这个数组 必须结果是 20
int a[8]={1, -2, 3, 10, -4, 7, 2, -5}; //这个数组 必须 结果是 18
// int a[10]={-1,-2,-3,-4,-5,-6,-7,-8,-9,-10};
printf("%d\n",get_sub_sum_max(a,8));
return 0;
}
int a[8]={ 1, -2, 3, 10, -4, 7, 2, -5};
max=1;sum=1
max=1;sum=-1 -->sum=0
max=3;sum=3
max=13;sum=13
max=13;sum=9
max=16;sum=16
max=18;sum=18
max=18;sum=13
返回 max=18
这里给出了详细解答:http://blog.csdn.net/v_JULY_v/article/details/6444021
分享到:
相关推荐
Labview应用技术 使用数组函数寻找数组中负数个数(拓展).docx 学习资料 复习资料 教学资源
简单数组赋值简单的 Java 应用程序,用于从数组中分离正数和负数并将它们放入单独的数组中。 还显示原始数组中的重复数和零数。 该作业是为塞尔维亚 IT 学院的 Core Java 课程完成的米洛斯·乌尔巴诺维奇,7.2015。 ...
给定一个n个元素的数组,数组元素全部为整数,负数,正数和0均有可能存在,设设计一个算法,找出连续的几个数组元素相乘积最大
算法小程序,将数组中所有的负数置于正数前
资源包括:源代码+详细设计报告+使用说明。 设计一台嵌入式CISC模型计算机, 输入包含5个整数(有符号数)的数组M,输出所有负数的平方和。
人民邮电出版社汇编教材(王庆生)实验3第2题答案
用汇编语言实现统计一个数组中正数负数零的个数。汇编代码
求一个长为N(小于255)的ARRAY字数组中正数、负数与零的个数,正数的个数存放在DH中,负数的个数存放在DL中,零的个数存放在BH中。(扩展:将统计的结果显示出来)
将正数转换成负数,负数转换成正数, int main(int argc, char* argv[]) { float k; c.f=-10; k=0-c.f; printf("k=%f\n",k); printf("Hello World!\n"); return 0; }
汇编键盘输入20个数,将其放在三个数组中,输入的一个,正数一个,负数一个。正数求和输出,负数求个数。
将-8到1的16个数放入30H开始的RAM区,其中正数、负数分别送40H和50H开始的存储单元,正数、负数和零的个数分别送到单元60H,61H,62H。
1.将数组分成正数和负数2.16位无符号排序3.七段码4.产生随机数5.字程序编制。汇编语言编制的简单程序,适合初学者
《正数和负数》导入
一、请编制程序,其功能是:将内存中由SOURCE指示的40个字节有符号数组成的数组分成正数和负数两个数组,并求这两个数组的数据个数,结果存放在RESULT指示的内存区域,存放形式为正数个数在前,其后跟正数数组元素,...
循环程序设计实验 试编程统计数据区中正数、零和负数的个数
.求子数组的最大和 题目: 输入一个整形数组,数组里有正数也有负数。 数组中连续的一个或多个整数组成...例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此输出为该子数组的和18。
一、请编制程序,其功能是:将内存中由SOURCE指示的40个字节有符号数组成的数组分成正数和负数两个数组,并求这两个数组的数据个数,结果存放在RESULT指示的内存区域,存放形式为正数个数在前,其后跟正数数组元素,...
一段代码,队列,实现负数赶正数的功能
初一正数与负数提高练习题及答案精选.doc
正数负数练习题.doc