LeetCode 53. 最大子序和

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

示例:

• 输入: [-2,1,-3,4,-1,2,1,-5,4]
• 输出: 6
• 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解题思路：

实现局部最大推导出来全局最大的子序和

从代码角度上来讲：遍历 nums，从头开始用 count 累积，然后计算出当前count和result的最大赋值给result，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。

那么如何切换区间呢？

// 取区间累计的最大值（相当于不断确定最大子序终止位置）
sum = Math.max(sum, count); 

代码实现：

方法一：

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null){
            return 0;
        }
        if(nums.length == 0){
            return nums.length;
        }

        int result = Integer.MIN_VALUE;
        int count = 0;
        for(int i = 0;i < nums.length;i++){
            count += nums[i];
            result = Math.max(count,result);

            if(count < 0){
                count = 0;
            }
        }
        return result;
    }
}

这种方法的关键在于使用 count 变量来记录当前的连续子数组和，并随时更新最大和 result。当 count 变为负数时，将其重置为 0 的目的是舍弃之前的负数和，重新从下一个元素开始计算连续子数组和。

这段代码的时间复杂度为 O(n)，其中 n 是数组的长度。通过一次遍历数组，即可找到最大和的连续子数组。

方法二：

public class MaximumSubarray {
    public static int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}

代码跟踪：

当输入数组为 [-2, 1, -3, 4, -1, 2, 1, -5, 4]时，我们可以使用表格来清晰地展示每一步的计算过程。下面是一个示例：

根据上面的计算过程，最大和为6。