题目已经把描述的比较清楚了，这里的子数组是连续的。
基本设计思想：
对于数组A[n]，顺序扫描数组中的每一个元素，利用s代表到当前元素为止的前面所有元素之和，并存储到当前位置为止各个位置s的最小值min。找出各个位置s-min的最大值，即为所求子数组最大值。
算法实现：
int maxArraySum (int A[],int n) {
int minsum,maxsum;
if (A[0]<0) minsum = A[0];
else minsum = 0;
maxsum = A[0];
for (int i = 1; i<n; i++) {
s += A[i];
if (maxsum<s-minsum)
maxsum = s-minsum;
else if (s<minsum)
minsum = s;
}
}
算法时间复杂度O(n)，空间复杂度O(1)
解释及证明：
这道题目第一反应应该是搜索所有的子数组，并求其中的最大值。可以模拟子数组的初末位置，并对子数组求和，时间复杂度至少是O(n^2)，我的思路是这样的，我们可以只模拟子数组一端的情况，我这里以末端为例。
对于这样的一个数组
Array(-2,5,3,-6,4,-8,6)
我们很容易可以想到以第i个位置为开始，以第j个位置为结尾的子数组，它的和可以用前j个元素之和减去前i-1个元素之和。我将前i个元素之和设为s[i]。比如这个数组，A[2...4]=sum[4]-sum[1]=0-(-2)=2。那么以第j个元素为结尾的子数组，它的和的最小值一定是sum[j]-min{sum[i]} (0<=i<j sum[0]=0)。那么我们只需遍历j，就可以找到结果。
编程之美书上的方法和我的不太相同。他的做法是考虑A[i]，A[i]可以单独构成子数组，也可以和之前或之后的元素构成子数组。我们对于任意位置i,记录前i个元素中子数组之和的最大值max和包括第i-1个位置的子数组的最大值start。对于第i个位置，我们有两个选择，以i为起始位置或者将第i个元素加入之前的数组，此时start更新为max{start+A[i],A[i]}。如果新的start>max，就更新max=start。
两种方法时间复杂度和空间复杂度均相同，不过我认为我的算法更容易理解一下。
