图解LeetCode——53. 最大子数组和

一、题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

二、示例

2.1> 示例 1：

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

2.2> 示例 2：

【输入】nums = [1]
【输出】1

2.3> 示例 3：

【输入】nums = [5,4,-1,7,8]
【输出】23

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 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)/ ~ 「干货分享，每天更新」