42 连续子数组的最大和

剑指 Offer 42. 连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。

解题思路：

假设 $sum(i-1)$ 表示数组 $nums$ 在 $[0, i-1]$ 区间的最大和

• 如果 $sum(i-1) < 0$ ，那么在计算 $sum(i)$ 时，就需要把 $sum(i-1)$ 抛弃。因为 $sum(i-1)$只会带来负贡献，即 $sum(i-1) + nums[i] < nums[i]$ ，因此 $sum(i) = nums[i] $时最好的选择。
• 如果 $sum(i-1) \geq 0$，那么在计算 $sum(i)$ 时，存在 $sum(i-1) + nums[i] \geq nums[i]$ 的情况，因此 $ sum(i) = sum(i-1) + nums[i]$ 是最好的选择。

代码：

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int ans = Integer.MIN_VALUE;
    int curSum = 0;
    for (int i = 0; i < nums.length; i++) {
        if (curSum < 0) {
            // 如果 curSum 已经小于0了，那么此时 curSum += nums[i] 的话，
            // 对 nums[i] 回造成负贡献，因此摒弃之前的子数组和，从 nums[i] 开始重新计算
            curSum = nums[i];
        } else {
            curSum += nums[i];
        }
        ans = Math.max(curSum, ans);
    }
    return ans;
}

复杂度分析

• 时间复杂度$O(N)$：$N$ 为数组的元素个数。
• 空间复杂度$O(1)$：使用常数大小的额外空间。