给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
这道题有点难度 我的这个代码超时了
int max = Integer.MIN_VALUE; int min = 0; for(int i = 0; i < nums.length; i++){ for(int j = i; j < nums.length; j++){ min = 0; for(int k = i; k < j+1; k++){ min += nums[k]; } if(min > max) max = min; } } return max;将上面的代码进行优化，只用两层循环，改成这样的，就是说外层是对所有元素起点的循环，内层是对所有元素的总和进行求和计算，在进行计算求和的过程中，不断和max进行比较，如果发现其值大于max则更新max的值 代码如下，但是也是刚刚通过了，打败了10%…
int max = Integer.MIN_VALUE; int min = 0; for(int i = 0; i < nums.length; i++){ min = 0; for(int j = i; j < nums.length; j++){ min +=nums[j]; if(max < min){ max = min; } } } return max;尝试使用递归来进行解决 首先就是最大要么出现在 1、左半部分 2、右半部分 3、包含了中间的元素
public static int maxSubsequenceSum(int[] a, int left, int right) { if(left == right) { //Base case if(a[left] > 0) { return a[left]; } else { return 0; //保证最小值为0 } } int center = (left+right)/2; int maxLeftSum = maxSubsequenceSum(a, left, center); //递归调用，求左部分的最大和 int maxRightSum = maxSubsequenceSum(a, center+1, right);//递归调用，求右部分的最大和 int leftBorderSum = 0, maxLeftBorderSum = 0;//定义左边界子序列的和 for(int i=center; i>=left; i--) {//求左边界的最大和（从右边开始往左求和） leftBorderSum += a[i]; if(leftBorderSum > maxLeftBorderSum) { maxLeftBorderSum = leftBorderSum; } } int rightBorderSum = 0, maxRightBorderSum = 0;//定义右边界子序列的和 for(int i=center+1; i<=right; i++) {//求右边界的最大和（从左边开始往右求和） rightBorderSum += a[i]; if(rightBorderSum > maxRightBorderSum) { maxRightBorderSum = rightBorderSum; } } //选出这三者中的最大值并返回（max3(int a, int b, int c)的实现没有给出） return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum); }转https://my.oschina.net/itblog/blog/267860 看一下排名靠前的代码，看看别人是怎么想的
首先定义一个长度为nums数组长度的数组subSums 遍历序列的时候对Sum进行累计，如果Sum累积后小于0的话就把Sum重置为下一个数字，每次更新Sum的最大值。最后便能求出最大值。其实这个算法就是把序列分为好几块，每一块满足：对于任意k，前k个数的和不会小于0（小于0就会分裂成两块了），当前i个数的和大于最大值时就进行更新，而最大值的左边界就是该块序列的第一个，右边界是第i个。时间复杂度为O(n)，而且可以一边读取一边处理，不需要开辟数组来存，空间也很省
摘自https://blog.csdn.net/samjustin1/article/details/52043369 还需要好好琢磨一下
int subSums = nums[0]; int max = subSums; for (int i=1; i<nums.length; i++) { subSums = subSums > 0 ? subSums + nums[i] : nums[i]; if (subSums > max) { max = subSums; } } return max; return max; } }动态规划解法 dp做法是很普遍的做法，只要想出状态转移方程就可以很快做出来了。 状态转移方程：sum[i] = max{sum[i-1]+a[i],a[i]}. (sum[i]记录以a[i]为子序列末端的最大连续和。)在dp的过程中便可以更新sum数组的最大值以及两个边界。 其实完全可以不用开数组，累计sum直到sum + a < a，把sum赋值为a，更新最大值就行了。你会发现这跟第4种方法是一样的。。。只是判断条件不一样，一个是sum <= 0一个是sum + a < a。。。（其实是一样的。。。） https://blog.csdn.net/samjustin1/article/details/52043369 代码跟第四种基本一样
