题目

给你一个整数数组 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) 的解法，尝试使用更为精妙的 分治法 求解。

解法

暴力解法

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

复杂度为O(N²)，超出时间限制，思考其他解法。

解法一 前缀和数组 + 最小前缀和

求子数组和，立马想到用 前缀和来解决

因为要找最大的子数组和，可以记录最小的前缀和，因为下图中绿色是被减的，当然越小越好。

class Solution {
    public int maxSubArray(int[] nums) {
        // 前缀和
        // 保存前面的最小前缀和,初始化为0，也就是从头到尾
        int preSum = 0, minPreSum = 0, maxSum = Integer.MIN_VALUE;
        
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            maxSum = Math.max(maxSum, preSum - minPreSum);
            minPreSum = Math.min(preSum, minPreSum);
        }
        return maxSum;
    }
}

时间复杂度当然是O(N)，表现特别好

解法二 动态规划

本题还可以用动态规划来解决

class Solution {
    public int maxSubArray(int[] nums) {
        // 动态规划
        // dp数组含义：保存i元素之前（包括i元素）的最大子数组和
        int[] dp = new int[nums.length];
        int result = nums[0];
        dp[0] = nums[0];
  
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            if (result < dp[i]) result = dp[i];
        }

        return result;
    }
}

时间复杂度同样为O(N)

小结

看到关键字子数组和，一定要联想到前缀和的解决方案。