本文主要是介绍LeetCode Maximum Subarray和编程之美 求数组的子数组之和的最大值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
一个含有N个整数的一维数组，求这个数组的子数组的最大值是多少？
题意：
1. 子数组，必须连续。
2. 求和，并不需要返回具体子数组的位置。
3. 数组的元素为整数，那么就有可能有正整数、0和负整数。
ex:
[1,-2,3,5,-3,2]返回8. 考虑用分治算法，也就是采用从数组的末尾开始往前遍历，如果已知(A[1]......A[n-1])中含有和最大的一段数组之和为All[1],并且已经知道(A[1]......A[n-1])中包含A[1]的和最大的一段数组为Start[1]，因为要保证子数组的连续，所以单独考虑这个Start数组，然后就可以分成三种情况来考虑：
max{A[0],A[0]+Start[1],All[1]},其实仔细想想也是可以理解的，就是从尾巴开始往前遍历，这样数组的时间复杂度就为O(n)
代码如下：
public int max(int x,int y)
{return (x> y) ? x : y;
}
public int MaxSum(int[] a,int n)
{int[] Start = new int[n];int[] All = new int[n];Start[n-1] = a[n-1];All[n-1] = a[n-1];for(int i = n - 2; i >= 0; i--){Start[i] = max(a[i],Start[i+1]); //这里先比较A[0]和(A[1]......A[n-1])中包含A[1]的和最大的一段数组为Start[1]，求其中最大的那个值All[i] = max(Start[i],All[i+1]); //这里再比较上面的那个两个的最大值和(A[1].....A[n-1])中的最大一段数组的值比较，求其中最大的那个}return All[0];
}这篇关于LeetCode Maximum Subarray和编程之美 求数组的子数组之和的最大值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
