给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
【输入】nums = -2,1,-3,4,-1,2,1,-5,4 【输出】6 【解释】连续子数组 4,-1,2,1 的和最大,为 6
【输入】nums = 1 【输出】1
【输入】nums = 5,4,-1,7,8 【输出】23
1
<= nums.length <= 10^5
-10^4
<= numsi <= 10^4
根据题目要求,我们需要获得一个给定数组nums
中的最大连续子数组和,这里面有两个重要的信息:
【信息1】连续子数组 【信息2】最大的和
既然是这样,那么我们以nums = [-2, 1, -3]
为例,来看一下按照模拟拆分子数组的情况下,怎么能够计算出来最大连续子数组的和。此处为了便于拆分子数组,我们以某元素作为当前子数组的最末尾元素进行拆分,可以得到如下拆分结果:
【以-2为结尾】只能拆分出1个子数组,即:
[-2]
;那么在当前这一个子数组中,最大数组和就是-2
了; 【以1为结尾】可以拆分出2个子数组,即:[-2, 1]
和[1]
;那么在当前这两个子数组中,最大数组和就是1
了; 【以-3为结尾】可以拆分出3个子数组,即:[-2, 1, -3]
、[1, -3]
和[-3]
;那么在当前这三个子数组中,最大数组和就是-2
了; 【结论】最终最大数组和就是1;
为了便于大家理解,下图我画出了具体的操作过程,具体详情,请见下图所述:
但是,对于上面的这种模拟分组计算来说,nums
数组中元素较少时是没问题的,但是如果元素很多,则执行效率就会非常低。那么有没有其他效率更高的算法呢?答案一定是有的。因为我们发现,本题需要求解出来的只是一个最大数组和,而并非要获取到最大数组和所对应的数组,所以我们可以采用动态规划的解题方式来解决这道题。
那么我们来分析一下,当要计算nums
数组中第i
个位置最大数组和的时候,其实我们只需要关注两个值:
【值1】当前元素
nums[i]
【值2】以元素nums[i-1]
为结尾的所有子数组中的最大数组和pre; 【结论】pre =Math.max(nums[i], nums[i] + pre)
; result =Math.max(result, pre)
;
状态转移方程也就是我们在上面结论中所描述的,那么,下面我们还是以nums = [-2, 1, -3]
为例,采用动态规划的方式,来重新计算一下最大连续子数组的和,具体详情,请见下图所述:
class Solution {
public int maxSubArray(int[] nums) {
int result = nums[0], pre = 0;
for (int num: nums) {
pre = Math.max(num, pre + num);
result = Math.max(result, pre);
}
return result;
}
}
今天的文章内容就这些了:
写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。