013.最大子数组和

53. 最大子数组和

给你一个整数数组 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) 的解法，尝试使用更为精妙的 分治法 求解。

题目思路

贪心思想：贪心思想（Greedy Algorithm）是一种解决优化问题的方法，它的核心思想是：每次选择当前看起来最优的解（即最有利的选项），希望通过局部最优的选择能够最终得到全局最优的解。贪心算法通常比较简单且高效，但并不是所有问题都适用，因为局部最优解不一定能导致全局最优解。

贪心算法的一般步骤是：

1. 选择问题的一个局部最优解。
2. 对剩下的问题继续应用贪心选择策略。
3. 直到问题解决。

对应到本题，我们使用贪心算法的核心思想就是：累加 nums 数组，但是如果累加和小于 0，则从下一位重新开始累加**（因为只要是小于 0，则对后面就只起到拉小值的副作用）**在累加过程中记录之前的最大累加和

**局部最优：**当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

**全局最优：**选取最大“连续和”

图中的 result 就是用于中累加过程中记录之前的最大累加和

红色的起始位置就是贪心每次取 count 为正数的时候，开始一个区间的统计。

题解代码

/*
    核心思想就是，累加nums数组，但是如果累加和小于0，则从下一位重新开始累加
    （因为只要是小于0，则对后面就只起到拉小值的副作用）
    在累加过程中记录之前的最大累加和
*/
public int maxSubArray(int[] nums) {
    // 校验
    if (nums.length == 1) {
        return nums[0];
    }
    int max = Integer.MIN_VALUE; // 将max初始化为最小值
    int sum = 0; // 累加变量
    for (int num : nums) {
        sum += num;
        max = Math.max(sum, max);// 取区间累计的最大值（相当于不断确定最大子序终止位置）
        if (sum <= 0) {
            sum = 0; // 重置累加变量，相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
    }
    return max;
}