这是一个比较典型的说明算法效率差异的题目。最笨也是最简单的算法的效率是O（N＊N），如果注意到结果的可重复利用，可以实现O（N＊LogN）的算法，但是最优的计算复杂度是O（N）。无论如何至少要遍历一遍整个数组，所以不可能有O（1）的实现方法。上面大家给出了很多的算法，liukun提出的分治的方法，这个问题不应该是分治问题，用分治的方法只会把问题搞复杂，它的计算复杂度应该是O（N＊LogN）。唐仕强和黄文彬给出的都是O（N）的解决方案，没有太仔细看，但我想结果都应该是对的，有问题也是对一些特殊情况的处理上，譬如对全部是负数的特殊情况的考虑，但是这些不影响整个算法的解体思路。问题的关键是如何自然地写出O（N）的算法。下面给出一个思考该算法的思路。

首先将问题描述形式化如下：
1 记数组为 A，其元素从0到n－1。
2 数组A的子数组记为A［i，j］，表示［i，j］闭区间区域的子数组。
3 子数组A［i，j］的和记为SA［i，j］
4 问题目标是寻找S［i，j］的最大值，记为MaxS［0，n－1］
分析问题内在的性质，引入一个中间函数，
X［i］表示所有以i为右边界的子数组的集合，即｛A［0,i］，A［1,i］...A［i, i］｝
MaxX［i］＝ max（SA［j，i］），其中 j＝［0, i］，表示X［i］集合中最大的子数组的和。
MaxX［i］记录的是以i为右端点的最大子数组和。它显然符合以下递推公示，
MaxX［i］＝ Max［i－1］＋A［i］（Max［i－1］>= 0）
＝ A［i］ （Max［i－1］< 0）
所以MaxX［i］可以很容易计算，而最终的目标结果就是MaxX［i］的最大值
MaxS［0, n－1］ ＝ max（MaxX［i］），其中i＝［0, n－1］；

根据以上的分析，算法的代码实现就会比较自然流畅，java实现如下：

  int sum = A[0];
  

  int left = 0;
  

  int leftOfMax = 0;
  

  int rightOfMax = 0;
  

  int maxSum = A[0];
  

  for（int i = 1; i<A.length; i++){
  

  if(sum < 0){
  

  sum = A[i];
  

  left = i;
  

  }else{
  

  sum = sum + A[i];
  

  }
  

  

  if(sum > maxSum){
  

  maxSum = sum;
  

  leftOfMax = left;
  

  rightOfMax = i;
  

  }
  

  }
  

  

  //这里maxSum为目标结果，其所对应的子数组为A［leftOfMax, rightOfMax].