[leetcode数组系列]4 最大子序和

[leetcode数组系列]4 最大子序和

1二面记录

小蓝还是有点实力的，过五关斩六将来到了二面，并联系上了二面面试官。一段简单的介绍后让小蓝手撕并拍照发过去(纯靠想象)。

1Leetcode53最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

小蓝一看，心想首先需要找到所有的子数组，然后对子数组求和，最后比较。不是很清楚？没关系，下面具体阐述下！

01题目解析

因为我们涉及到数组和的比较，假设数组第一个元素为最终需要返回的值，定义为result。

遍历Nums寻找大于0的数，保留当前sum值并累加。如果当前数组元素num值小于0直接赋值给sum。

为什么寻找大于0？这是本题的关键。在此大家可以自行思考1分钟！文后解答，这样印象会更深刻哈。

每次对当前sum值和result比较，将较大值赋值给result。

result = max(sum, result)

题目虽简单，细品出真理！一定掌握哈！

为什么判断大于0？

如果遍历的数组元素全是负数(<0)，我们就取最大的负数。(-1)+(-1)=-2,-2<-1.负数只会越加越小。如果当前遍历的数组和为正数(>0),后面遇到一个负数就会导致原来的和变小，所以我们直接不要。

0

2

代码实现

1c++版本

2python版本

3java版本

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。