42 连续子数组的最大和

Lin2J
2021-07-21 / 0 评论 / 97 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 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)$:使用常数大小的额外空间。