题目已经把描述的比较清楚了，这里的子数组是连续的。

基本设计思想：

对于数组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。

两种方法时间复杂度和空间复杂度均相同，不过我认为我的算法更容易理解一下。