【力扣】53.最大子数组和 区别于盛水最多的水桶
Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。
春招打卡第21天第29篇。
勤学似春起之苗，不见其增，日有所长；辍学如磨刀之石，不见其损，日有所亏。
掘金的活动真多哇，这个月决定每天用go刷题，一方面提升一下算法水平，另一方面沉淀一下go语言的学习。
Let's GO!
题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 10510^{5}105
−104-10^{4}−104 <= nums[i] <= 10410^{4}104
题目分析
这道题和之前解答过的 水桶最多能盛多少水 有点像，水桶盛水最多的问题使用双指针是最优解。
这道题经过测试和演算，发现动态规划的思路是最优解：
我们可以把解题思路拆分为，每个节点都和上一个节点比较，即：是当前节点的值大？还是当前节点+前一个节点的值大？
把问题进行拆分，一直进行这种比较，最终获得最大的值。
思路讲解
- 初始化最大值max，因为从头开始，默认最大值就是数组下标为0时对应的值。
- 进行循环遍历，遍历数组长度的次数
- 在for循环中进行题目分析中的逻辑判断：
- 如果当前节点的值+前一个节点的值>当前节点的值：我们更新当前节点的值为前一个节点值+当前节点值。
- 在for循环中进行判断，如果相加后的当前节点值大于目前的最大值max，就更新max
- 一直进行循环判断直到结束
- 返回max即可，就是我们需要的最大子数组和
AC代码
go
func maxSubArray(nums []int) int { max := nums[0] for i := 1; i < len(nums); i++ { if nums[i] + nums[i-1] > nums[i] { nums[i] += nums[i-1] } if nums[i] > max { max = nums[i] } } return max }运行结果
总结
复杂度
时间复杂度：O(n)，其中n是输入数组的长度。
空间复杂度：O(1)，因为我们只需要常数空间来存放变量就可以了。
来源说明
来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/ma…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
最后
感谢阅读，欢迎大家三连：点赞、收藏、投币（关注）！！！