图解LeetCode——剑指 Offer 42. 连续子数组的最大和

一、题目

• 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

二、示例

2.1> 示例1:

【输入】 nums = [-2,1,-3,4,-1,2,1,-5,4]

【输出】 6

【解释】 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

• 1 <= arr.length <= 10^5
• -100 <= arr[i] <= 100

三、解题思路

• 根据题目描述，在一个有整数和负数的数组nums中，求得所有的子数组的和的最大值。那么，第一个解题思路就是：

【首先】计算出所有子数组；

【然后】计算每个子数组中的总和，再将最大的总和作为结果返回；

• 但是，这种解题方法时间复杂度会很高。那么，有没有更简单的解题思路呢？那么我们可以通过动态规划来解决这道题。首先，我们定义一个变量，即：preSum，用来表示以nums[i]为末尾的所有子数组中最大的总和。我们通过遍历nums数组中的每个元素，来依次计算preSum的值，那么最大的值也就是这道题的答案了。
• 在对比过程中，有如下逻辑：

【情况1】如果nums[i]的值大于它前一个元素i-1的preSum的值，并且该preSum值小于0，则i位置的preSum就是nums[i]；

【情况2】否则，位置i的preSum值就等于nums[i] + 元素i-1的preSum的值

• 为了方便理解，我们以输入：nums=[-2,1,-3,4,-1]为例，看一下具体的执行过程是怎么样的，具体图例请见如下所示：

四、代码实现

classSolution {
publicintmaxSubArray(int[] nums) {
intpreSum=nums[0], result=preSum;
for (inti=1; i<nums.length; i++) {
if (nums[i] >preSum&&preSum<0) preSum=nums[i];
elsepreSum+=nums[i];
result=Math.max(result, preSum);
        }
returnresult;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」