[每天一道 Leetcode] 53. 最大子序和

题目

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

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

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

题解

动规的经典题目。遍历数组，累加，当累加的值小于 0 时，从下一元素开始再从新累加。在这个过程中记录下最大的累加值就可以了。

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

这个题目还让用分而治之的方法，那怎么分治呢?具有最大和的子序列存在于一下三种情况之中：

1. 该最大和子序列存在于其上一级子序列的左半部分中

2. 该最大和子序列存在于其上一级子序列的右半部分中

3. 该最大和子序列存在于其上一级子序列的中间部分（既从中间点向左右延伸的序列）

情况 1 和情况 2 可以通过迭代（ recursion ）解决。

情况 3 可以通过由中间节点开始，向左计算左半部分的和的最大值，向右计算右半部分的和的最大值，然后叠加得到。这种方法需要 O(n)时间。

该段代码运行时间符合 T(n) = 2*T(n/2) + O(n)。

class Solution {
    public int maxSubArray(int[] nums) {
        return maxSubArray(nums, 0, nums.length - 1);
    }

    public int maxSubArray(int[] nums, int left, int right) {
        if (left > right) {
            return Integer.MIN_VALUE;
        } else if (left == right) {
            return nums[left];
        } else {
            int middle = (right - left) / 2 + left;
            int leftMax = maxSubArray(nums, left, middle);
            int rightMax = maxSubArray(nums, middle + 1, right);
            int sum = 0;
            int maxToLeft = Integer.MIN_VALUE;
            for (int i = middle; i >= left; i--) {
                sum += nums[i];
                maxToLeft = Math.max(maxToLeft, sum);
            }
            sum = 0;
            int maxToRight = Integer.MIN_VALUE;
            for (int i = middle + 1; i <= right; i++) {
                sum += nums[i];
                maxToRight = Math.max(maxToRight, sum);
            }
            int result = maxToLeft + maxToRight;
            result = Math.max(result, leftMax);
            result = Math.max(result, rightMax);
            return result;
        }
    }
}

热门阅读

• [ HTTP ] 分布式 session 的管理
• [ Leetcode ] 52. N 皇后 II

最近在刷题，有一起的可以加手撕代码群：805423079