代码随想录Day26 贪心01 LeetCode T53 最大子数组和

LeetCode T53 最大子数组和

题目链接:53. 最大子数组和 - 力扣（LeetCode）

题目思路:

贪心贪的是哪里呢？

如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

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

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

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

从代码角度上来讲：遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。

这相当于是暴力解法中的不断调整最大子序和区间的起始位置。

定义变量:

count:记录局部和

sum:记录目前出现的最大和

思路:一层for循环遍历数组,每次遇到连续子数组之和为负数的时候,就从下一个元素继续开始叠加,每次叠加一个元素对sum进行一次更新.

题目代码:

class Solution {
    public int maxSubArray(int[] nums) {
        int count = 0;//目前值
        int sum = Integer.MIN_VALUE;//目前出现的最大值
        for(int i = 0;i<nums.length;i++)
        {
            count+=nums[i];
            sum = Math.max(count,sum);
            if(count < 0)
            {
                count = 0;
            }
        }
        return sum;
    }
}