描述

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

示例 1：

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

输入：nums = [1]
输出：1
示例 3：

输入：nums = [0]
输出：0
示例 4：

输入：nums = [-1]
输出：-1
示例 5：

输入：nums = [-100000]
输出：-100000

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

做题

这道题，在学校的时候，老师讲过，依稀记得，是在学习动态规划的时候学的。

解法是，遍历数组，然后从头到尾一个一个把数值加起来，把 sum 都存起来，当下一个sum 比现在的 max 大时，就替换掉，这里是为了寻找最大值；如果如果当前的 sum 小于 0，就把之前的 sum 丢掉，就把当前的值赋给 sum，从下一个数开始求和，这里是为了求和，求一个可能最大的和，是否是最大，那就需要我们前面的逻辑去判断了。

思路大概是这样，敲代码。

public int maxSubArray(int[] nums) {
    if (nums==null||nums.length==0){
        return 0;
    }
    int max=nums[0];
    int sum=0;
    for (int i = 0; i < nums.length; i++) {
        if (sum>0){
            sum+=nums[i];
        }else {
            sum=nums[i];
        }
        if (sum>max){
            max=sum;
        }
    }
    return max;
}

分治法，我看了一下力扣上的解析，我也尝试地去解释了一下它的原理是什么，但是我觉得我怎么表达（敲了几百个字最后全删了）都没有力扣官方解释的好，所以感兴趣的小伙伴可以去看看力扣官方的讲解，我就不在这里献丑了。

力扣官方讲解

今天就到这里了。

这里是程序员徐小白，【每日算法】是我新开的一个专栏，在这里主要记录我学习算法的日常，也希望我能够坚持每日学习算法，不知道这样的文章风格您是否喜欢，不要吝啬您免费的赞，您的点赞、收藏以及评论都是我下班后坚持更文的动力。