8.3最大自序和（LC53-M）

算法：

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

（-2+1，起点为负数，加上后面的数，只会让和变小；不如让1变成新的起点，再往后求和）

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

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

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

正确代码：

class Solution {
    public int maxSubArray(int[] nums) {
        //考虑特殊情况：示例2
        if(nums.length==1){
            return nums[0];
        }
        // count用来统计循环过程中的动态变化的和，若和为负数，
        //就把count更新为0，相当于从下一个数重新开始
        int count = 0;
        //result是我们要求的连续子数组的最大和
        int result = Integer.MIN_VALUE;


        for (int i=0; i<nums.length; i++){
            count +=nums[i];
            //取区间累计的最大值（相当于不断确定最大子序终止位置）
            //这也是为什么result的初值要设置为很小的数
            result = Math.max(result ,count);


            if (count <= 0){
                count = 0;
         // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
            }
        }
        return result;        

    }
}

注意：

1.int result = Integer.MIN_VALUE;? ? ?

MIN_VALUE全部大写

时间空间复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(1)