Leetcode#53.Maximum Subarray（最大子序和）

题目描述

给定一个序列（至少含有 1 个数），从该序列中寻找一个连续的子序列，使得子序列的和最大。

例如，给定序列 [-2,1,-3,4,-1,2,1,-5,4]，
连续子序列 [4,-1,2,1] 的和最大，为 6。

扩展练习:

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

思路

思路一：
maxSum 必然是以numsi结尾的某段构成的，也就是说maxSum的candidate必然是以nums[i]结果的。如果遍历每个candidate，然后进行比较，那么就能找到最大的maxSum了。

假设把nums[i]之前的连续段叫做sum。可以很容易想到:

1. 如果sum>=0，就可以和nums[i]拼接在一起构成新的sum。因为不管nums[i]多大，加上一个正数总会更大，这样形成一个新的candidate。
2. 反之，如果sum<0，就没必要和nums[i]拼接在一起了。因为不管nums[i]多小，加上一个负数总会更小。此时由于题目要求数组连续，所以没法保留原sum，所以只能让sum等于从nums[i]开始的新的一段数了，这一段数字形成新的candidate。
3. 如果每次得到新的candidate都和全局的maxSum进行比较，那么必然能找到最大的max sum subarray.

在循环过程中，用maxSum记录历史最大的值。从nums[0]到nums[n-1]一步一步地进行。

思路二：
遍历array，对于每一个数字，我们判断，（之前的sum + 这个数字） 和 （这个数字） 比大小，如果（这个数字）自己就比 （之前的sum + 这个数字） 大的话，那么说明不需要再继续加了，直接从这个数字，开始继续，因为它自己已经比之前的sum都大了。

反过来，如果 （之前的sum + 这个数字）大于 （这个数字）就继续加下去。

利用动态规划做题。
只遍历数组一遍，当从头到尾部遍历数组A， 遇到一个数有两种选择 （1）加入之前subArray （2）自己另起一个subArray

设状态S[i], 表示以A[i]结尾的最大连续子序列和，状态转移方程如下:

S[i] = max(S[i-1] + A[i],A[i])

从状态转移方程上S[i]只与S[i-1]有关，与其他都无关，因此可以用一个变量来记住前一个的最大连续数组和就可以了。这样就可以节省空间了。

代码实现

package Array; /** * 53.Maximum Subarray（最大子序和） * 给定一个序列（至少含有 1 个数），从该序列中寻找一个连续的子序列，使得子序列的和最大。 * 例如，给定序列 [-2,1,-3,4,-1,2,1,-5,4]， * 连续子序列 [4,-1,2,1] 的和最大，为 6。 */ public class Solution53 { public static void main(String[] args) { Solution53 solution53 = new Solution53(); int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; System.out.println(solution53.maxSubArray(arr)); } /** * maxSum 必然是以nums[i](取值范围为nums[0] ~ nums[n-1])结尾的某段构成的，也就是说maxSum的candidate必然是以nums[i]结果的。如果遍历每个candidate，然后进行比较，那么就能找到最大的maxSum了。 * 假设把nums[i]之前的连续段叫做sum。可以很容易想到: * 1. 如果sum>=0，就可以和nums[i]拼接在一起构成新的sum。因为不管nums[i]多大，加上一个正数总会更大，这样形成一个新的candidate。 * 2. 反之，如果sum<0，就没必要和nums[i]拼接在一起了。因为不管nums[i]多小，加上一个负数总会更小。此时由于题目要求数组连续，所以没法保留原sum，所以只能让sum等于从nums[i]开始的新的一段数了，这一段数字形成新的candidate。 * 3. 如果每次得到新的candidate都和全局的maxSum进行比较，那么必然能找到最大的max sum subarray. * 在循环过程中，用maxSum记录历史最大的值。从nums[0]到nums[n-1]一步一步地进行。 * * @param nums * @return */ public int maxSubArray(int[] nums) { int sum = 0; //或者初始化为 sum = INT_MIN 也OK。 int maxSum = nums[0]; for (int i = 0; i < nums.length; i++) { if (sum >= 0) { sum += nums[i]; } else { sum = nums[i]; } if (sum > maxSum) { maxSum = sum; } } return maxSum; } /** * 遍历array，对于每一个数字，我们判断，（之前的sum + 这个数字） 和 （这个数字） 比大小，如果（这个数字）自己就比 （之前的sum + 这个数字） 大的话，那么说明不需要再继续加了，直接从这个数字，开始继续，因为它自己已经比之前的sum都大了。 * 反过来，如果 （之前的sum + 这个数字）大于 （这个数字）就继续加下去。 * 利用动态规划做题。 * 只遍历数组一遍，当从头到尾部遍历数组A， 遇到一个数有两种选择 （1）加入之前subArray （2）自己另起一个subArray * 设状态S[i], 表示以A[i]结尾的最大连续子序列和，状态转移方程如下: * S[i] = max(S[i-1] + A[i],A[i]) * 从状态转移方程上S[i]只与S[i-1]有关，与其他都无关，因此可以用一个变量来记住前一个的最大连续数组和就可以了。 * 这样就可以节省空间了。 * 时间复杂度：O(n) 空间复杂度：O(1) */ public int maxSubArray_2(int[] nums) { int sum = 0; //或者初始化为 sum = INT_MIN 也OK。 int maxSum = nums[0]; //动态规划 for (int i = 0; i < nums.length; i++) { sum = Math.max(sum + nums[i], nums[i]); maxSum = Math.max(sum, maxSum); } return maxSum; } }