[每天一道 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