数组--53.最大子数组和/medium

1、题目

给你一个整数数组 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 <= 105
-104 <= nums[i] <= 104

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

2、题目分析

求连续子数组的最大和，意味着对数组切分成多段，此时有 2 个要点：

1. 如何切分，什么情况下子数组还能接着往后连续下去？
   求连续子数组的最大和，当子数组遇到新值时，
   如果加该值，子数组的和大于该值，则让子数组继续往下遍历的效果更佳，
   如果加该值，子数组的和小于该值，则不如让子数组在这做分割，然后下一个子数组从该新值开始。
2. 对切分后的每一段数据做什么操作？
   进行值的累加，并对比记录下各段子数组和的最大值。

3、解题步骤

1. 初始化 2 个值：
   a. 每段子数组的和=0
   b. 各段子数组和的最大值max=数组首个元素（不能初始化为0，避免数组各段子数组和的最大值小于0的情况）
2. 遍历数组，并做 2 步：
   a. sum = max(上个子数组 + 当前新值，当前新值)。即判断上个子数组是否还往下扩展，还是在此截止。
   b. max = max(sum, max)。即max对比记录下各段子数组和的最大值。

4、复杂度最优解代码示例

    public int maxSubArray(int[] nums) {
        int sum = 0;
        // 踩坑，这里不能初始化为 0。如当数组只有1个元素，且为负数时，max不会被替换为负数。
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
        	// a. sum = max(上个子数组 + 当前新值，当前新值)。即判断上个子数组是否还往下扩展，还是在此截止。
            sum = Math.max(sum + nums[i], nums[i]);
            // b. max = max(sum, max)。即max对比记录下各段子数组和的最大值。
            max = Math.max(sum, max);
        }
        return max;
    }

5、抽象与扩展

求连续子数组/子串的和值等问题，核心就是找到子数组/子串是否往下扩展的条件。

如本题中，
子数组要往下扩展的条件就是，子数组的和 + 新值 > 新值，则子数组接着往下扩展。
否则，新值 另起一个子数组。