【正确答案】这是一道非常经典的在笔试面试中碰到的算法题，有多种解决方法，下面分别从简单到复杂逐个介绍各种方法。
   方法一：蛮力法
   最简单也是最容易想到的方法就是找出所有的子数组，然后求出子数组的和，在所有子数组的和中取最大值。实现代码如下：
   def maxSubArray(arr):
   if arr==None or len(arr)＜1:
   print "参数不合法"
   return
   ThisSum=0
   MaxSum=0
   i=0
   while i＜len(arr):
   j=i
   while j＜len(arr):
   ThisSum=0
   k=i
   while k＜j:
   ThisSum+=arr[k]
   k+=1
   if ThisSum＞MaxSum:
   MaxSum=ThisSum
   j+=1
   i+=1
   return MaxSum
   
   if __name_=="_main_":
   arr=[1,-2,4,8,-4,7,-1,-5]
   print "连续最大和为:"+str(maxSubArray(arr))
   程序的运行结果为：
   连续最大和为：15
   算法性能分析：
   这种方法的时间复杂度为O(n³)，显然效率太低，通过对该方法进行分析发现，许多子数组都重复计算了，鉴于此，下面给出一种优化的方法。
   方法二：重复利用已经计算的子数组和
   由于Sum[i,j]=Sum[i,j-1]+arr[j]，在计算Sum[i,j]的时候可以使用前面已计算出的Sum[i,j-1]而不需要重新计算，采用这种方法可以省去计算Sum[i,j-1]的时间，因此，可以提高程序的效率。
   实现代码如下：
   def maxSubArray(arr):
   if arr==None or len(arr)＜1:
   print "参数不合法"
   return
   maxSum=-2**31
   i=0
   while i＜len(arr):
   sums=0
   j=i
   while j＜len(arr):
   sums+=arr[j]
   if sums＞maxSum:
   maxSum=sums
   j+=1
   i+=1
   return maxSum
   
   if __name__=="__main__":
   arr=[1,-2,4,8,-4,7,-1,-5]
   print "连续最大和为:"+str(maxSubArray(arr))
   算法性能分析：
   这种方法使用了双重循环，因此，时间复杂度为O(n²)。
   方法三：动态规划方法
   可以采用动态规划的方法来降低算法的时间复杂度。实现思路如下。
   首先可以根据数组的最后一个元素arr[n-1]与最大子数组的关系分为以下三种情况讨论：
   (1)最大子数组包含arr[n-1]，即最大子数组以arr[n-1]结尾。
   (2)arr[n-1]单独构成最大子数组。
   (3)最大子数组不包含arr[n-1]，那么求arr[1...n-1]的最大子数组可以转换为求arr[1...n-2]的最大子数组。
   通过上述分析可以得出如下结论：假设已经计算出子数组arr[1...i-2]的最大的子数组和All[i-2]，同时也计算出arr[0...i-1]中包含arr[i-1]的最大的子数组和为End[i-1]。则可以得出如下关系：All[i-1]=max(End[i-1],arr[i-1]，All[i-2])。利用这个公式和动态规划的思想可以得到如下代码：
   def maxSubArray(arr):
   if arr==None or len(arr)＜1:
   print "参数不合法"
   return
   n=len(arr)
   End=[None]*n
   All=[None]*n
   End[n-1]=arr[n-1]
   All[n-1]=arr[n-1]
   End[0]=All[0]=arr[0]
   i=1
   while i＜n:
   End[i]=max(End[i-1]+arr[i],arr[i])
   All[i]=max(End[i],All[i-1])
   i+=1
   return All[n-1]
   
   if __name__=="__main__":
   arr=[1, -2, 4, 8, -4, 7, -1, -5]
   print "连续最大和为: "+str(maxSubArray(arr))
   算法性能分析：
   与前面几个方法相比，这种方法的时间复杂度为O(N)，显然效率更高，但是由于在计算的过程中额外申请了两个数组，因此，该方法的空间复杂度也为O(N)。
   方法四：优化的动态规划方法
   方法三中每次其实只用到了End[i-1]与All[i-1]，而不是整个数组中的值，因此，可以定义两个变量来保存End[i-1]与All[i-1]的值，并且可以反复利用。实现代码如下：
   def maxSubArray(arr):
   if arr==None or len(arr)＜1:
   print "参数不合法"
   return
   nAll=arr[0] #最大子数组和
   nEnd=arr[0] #包含最后一个元素的最大予数组和
   i=1
   while i＜len(arr):
   nEnd=max(nEnd+arr[i],arr[i])
   nAll=max(nEnd,nAll)
   i+=1
   return nAll
   
   if __name__=="__main__":
   arr=[1, -2, 4, 8, -4, 7, -1, -5]
   print "连续最大和为: "+str(maxSubArray(arr))
   算法性能分析：
   这种方法在保证了时间复杂度为O(N)的基础上，把算法的空间复杂度也降到了O(1)。

【答案解析】[考点] 如何求数组连续最大和