题目介绍

最大子数组和

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

子数组是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入*：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

分析

动态规划

这题有时间要求，所以我们需要在 O(n) 时间内解决问题。

所以我们考虑使用动态规划，我们维护一个用于记录以当前位置结尾的最大子数组和的数组maxArray[]。

动态更新规则是：
maxArray[i] = Math.max(maxArray[i-1] + nums[i], nums[i])
表示以当前位置结尾的最大子数组和，要么是前一个位置的最大子数组和加上当前位置的值，要么就是当前位置的值。

同时我们还需要维护一个记录最大值的变量max。

当数组更新到最后一个位置的时候，这个时候的max就是我们需要的值。

array[i] 仅和 array[i-1] 相关时的技巧

当我们的数组存在array[i] 仅和 array[i-1] 相关的情况时，我们可以使用滚动数组的技巧，将空间复杂度从 O(n) 降到 O(1)。

只维护一个当前值用于记录array[i-1]，并和下一个输入做合并形成array[i]。

实现

代码

代码如下：

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int cur = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(cur + nums[i], nums[i]);
            max = Math.max(max, cur);
        }
        return max;
    }
}

代码比较简单，但是注意使用了 Math.max 来更新 cur 和 max。

时间复杂度

时间复杂度为 O(n)，空间复杂度为 O(1)。

优化

分治法

这道题还可以使用分治法来解决。