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
分享到:
相关推荐
02第三章第四章D30-p59.ram 03第五章第五章P60-P85.rar 04第六章第章第八章P85-P8113.ram 05第九章第十章p114-P137.rar 06第十章第章P138-P165.rar 07第十■章第十■章D165-P185.ram 08第十三章第十四章p186-P218....
DAMA 数据治理工程师”(Certified Data Governance Associate 简称CDGA)考试,根据参加考试考生和专业机构汇编整理,分三种类型题目,适合不同情况的学生。 入门级:《CDGA试题混编88题》 进阶级:《CDGA试题混编88...
3.[答案V0.2版]精选微软数据结构+算法面试100题[前20题]--修正 http://download.csdn.net/source/2813890 //此份答案是针对最初的V0.1版本,进行的校正与修正。 4.[答案V0.1版]精选微软数据结构+算法面试100题[前25...
02 第三章 第四章P30-P59 03 第五章 第五章P60-P85 04 第六章 第七章第八章P85-P8113 05 第九章 第十章P114-P137 06 第十一章 第十二章P138-P165 07 第十二章 第十二章P165-P185 08 第十三章 第十四章P186-P218 09 ...
第1题【答案】 ...第3题【答案】 第1处:String[]args(或 String args[])(注:args为变量名,可为其他名称) 第2处:switch 第3处:r=r-6;break;(或r-=6;break;) 第4题【答案】 第1处:int MaxValue
Python基础题库100题及答案 Python基础题库100题及答案全文共16页,当前为第1页。Python基础题库100题及答案全文共16页,当前为第1页。 Python基础题库100题及答案全文共16页,当前为第1页。 Python基础题库100题及...
背题当然就是背前面说的南开100题啦,其实虽然号称100题,也不过10多个题型而已,这个在我提供的下载地址里已经分好类别了。把这些题型背下来就可以了;网络上有精简版以及笔者的背诵版可供参考。背诵要在理解的基础...
本微软面试100题系列,共计11篇文章,300多道面试题,截取本blog索引性文章:程序员面试、算法研究、编程艺术、红黑树、数据挖掘5大系列集锦:http://blog.csdn.net/v_july_v/article/details/6543438,中的第一部分...
昨日,11.19,最新整理了,第61...3.[答案V0.1 版]精选微软数据结构+算法面试100 题[前25 题] http://download.csdn.net/source/2796735 题目系列: 4.[第一部分]精选微软等公司数据结构+算法经典面试100 题[1-40 题] ...
同博文pdf版,方便有需求的同学下载查看,主要整理了 B站 尚硅谷 大厂面试题第三季 全部内容,整合笔记,包含【JUC】【Redis】【Spring】等保证收获满满
微软等数据结构+算法面试100题最后20题第81-100题新鲜出炉 ---100题系列V0.1版完整公布 作者:July 时间:2010年12月5日 ============= 首先,非常感谢各位,对本微软面试100题系列前期工作的大力支持。 很多很多...
希望通过这100道例题,能对python3的基础代码能力有一定的掌握。需要的朋友可下载试试! 目录 实例001:数字组合 实例002:“个税计算” 实例003:完全平方数 实例004:这天第几天 实例005:三数排序 实例006:...
CSP-J 第3套初赛模拟试题模拟题附答案
CCF考试第三题
操作系统第三章 存储管理 期末测试复习题及答案.pdf操作系统第三章 存储管理 期末测试复习题及答案.pdf操作系统第三章 存储管理 期末测试复习题及答案.pdf操作系统第三章 存储管理 期末测试复习题及答案.pdf操作系统...
算法设计与分析 吕国英 第三章第四章第五章课后习题答案
在此之前,由于本人笨拙,这微软面试100题的答案只整理到了前60题(第1-60题答案可到本人资源下 载处下载:http://v_july_v.download.csdn.net/),故此,常有朋友留言或来信询问后面40题的答案。只是 因个人认为:...
2020 CSP-S 第1轮 初赛 第 18 题 二、阅读程序题 第3题.pdf
北航数值分析大作业是每位北航学子上大学理学院学生,数值方面研究生所必须面对的大作业,在期末成绩...本文很完美的完成了北航数值第三次大作业,代码工整,简短,算法设计充实、正确。并且附上符合要求的计算结果。
计算机基础、网络基础、windows系统管理、windows服务器管理、Linux、SQL Server