求子数组的最大和

分析:输入一个整形数组,数组里有正数也有负数,数组中一个或连续的多个正数,求所有子数组的和的最大值。

当我们加上一个正数时,和会增加;当我们加上一个负数时,和会减少。如果当前得到的和是个负数,那么这个和在接下来的累加中应该抛弃并重新清零,不然的话这个负数将会减少接下来的和。

因此需采用DP思想,记录下当前元素之和(为其最优状态,既最大),将其与目前所得的最大和比较,若大于则更新,否则继续。状态的累加遵循这个过程:如果当前和小于0,则放弃该状态,将其归零。

扩展:数对之差的最大值

 1 //求子数组的最大和
 2 //利用的是dp的思想,依次遍历数组中的每个元素,把他们相加,如果加起来小于0,则
 3 //把当前元素之和清为0,否则则和最大和比较,更新最大和,最后得到必是子数组的最大和
 4 #include<iostream>
 5 using namespace std;
 6 
 7 int findGreatestSubSum(const int a[],const int size)
 8 {
 9     int curSum=0;
10     int maxSum=0;
11 
12     for(int i=0;i<size;i++)
13     {
14         curSum+=a[i];
15         if(curSum<0) 
16             curSum=0;   //放弃这个阶段,从新开始
17         if(curSum>maxSum) 
18             maxSum=curSum; //更新最大和
19     }
20 
21     if(maxSum==0)
22     {            //若是数组中的元素均为负数,则输出里面的最大元素
23         maxSum=a[0];          //当然这步也可以写到上面一个循环里
24         for(int i=1;i<size;i++)
25         {
26             if(maxSum<a[i]) 
27                 maxSum=a[i];
28         }
29     }
30     return maxSum;
31 }
32 
33 int main(void)
34 {
35     int a[]={1, -2, 3, 10, -4, 7, 2, -5};
36     int length=sizeof(a)/sizeof(int);
37 
38     cout<<findGreatestSubSum(a,length)<<endl;
39     system("pause");
40     return 0;
41 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python中文社区

Python生成器的使用技巧详解

之前我们介绍了列表解析式,他的优点很多,比如运行速度快、编写简单,但是有一点我们不要忘了,他是一次性生成整个列表。如果整个列表非常大,这对内存也同样会造成很大压...

14230
来自专栏求索之路

Effective Java笔记(不含反序列化、并发、注解和枚举)

最近把Effective Java复习了一遍,其中有比较多的java最佳实践可以在平时编程中用到。反序列化、并发、注解和枚举这四章没看,并发这本书里讲的比较简...

365110
来自专栏北京马哥教育

对Python老司机99%有帮助的简明语法总结乱编

本文由马哥教育Python实战开发班6期学员推荐,转载自互联网,作者为赖笔小新,感谢作者的辛苦付出和贡献。 最近发现进入python群的朋友都在你是如何自学py...

31670
来自专栏Python小屋

Python 3.6.x字符串格式化方法小结

1 使用%符号进行格式 使用%符号进行字符串格式化的形式如下图所示,格式运算符%之前的部分为格式字符串,之后的部分为需要进行格式化的内容。 ? Python...

31060
来自专栏青玉伏案

窥探Swift之使用Web浏览器编译Swift代码以及Swift中的泛型

   有的小伙伴会问:博主,没有Mac怎么学Swift语言呢,我想学Swift,但前提得买个Mac。非也,非也。如果你想了解或者初步学习Swift语言的话,你可...

19450
来自专栏Java 源码分析

数据结构Stack

​ 在很多应用中,我们需要维护多个对象的集合,这种操作非常简单。我们可能想要向集合中 加入某个元素,去掉某个元素,以及遍历 集合中的元素并对他们执行某种操...

34060
来自专栏机器之心

资源 | 忘了Python关键语句?这份备忘录拯救你的记忆

Python 3 Cheat Sheet 一共包含两页,分成了多个框图,涉及基本的 Python 数据结构、数学运算、条件和循环语句、文件读写,以及异常值处理等...

12930
来自专栏技术小站

Python 基础 (-)

Python 单词是“大蟒蛇”的意思。但是龟叔不是喜欢蟒蛇才起这个名字,而是正在追剧:英国电视喜剧片《蒙提·派森的飞行马戏团》(Monty Python and...

1.8K30
来自专栏北京马哥教育

Python2.x与3​​.x版本区别

? 文 | 豌豆 来源 | 菜鸟教程 Python的3.0版本,常被称为Python 3000,或简称Py3k。相对于Python的早期版本,这是一个较...

35660
来自专栏微信公众号:Java团长

Java知识点集锦

答:不是。Java中的基本数据类型只有8个:byte、short、int、long、float、double、char、boolean;除了基本类型(primi...

13310

扫码关注云+社区

领取腾讯云代金券