如[1,-2,4,-3]和最大的序列为[4]，和为 4，再比如[3,2,-4,5,-2]，和最大的序列为[3,2,-4,5]，和为6。
分析这就是求最大值的问题，从序列某一项开始，往后相加，找到和最大时返回结束位置索引，由于有n个元素，需要循环n遍，再比较这n个求和值谁最大。
#返回 从某项开始最大和时最后一项元素的下标
def func(L,s):
j=0
sum=0
maxsum=L[s]
for i in range(s,len(L)):
sum=sum+L[i]
if sum >= maxsum:
maxsum=sum
j=i
return [j,maxsum]
def findgreatsumofsublist(L):
j=0
start=end=0
maxsum=func(L,0)[1]
for i in range(0,len(L)):
temp=func(L,i)[1]
if maxsum <=temp:
maxsum=temp
start=i
end=func(L,i)[0]
return start,end,maxsum
测试用例
>>> findgreatsumofsublist([-1,-2,6,7,-6,5])
(2, 3, 13)
>>> findgreatsumofsublist([-1,-2,-3,-2])
(0, 0, -1)
>>>
这种最直观的方法，是一种暴力算法，枚举了数组的所有子数组，一个长度为n的数组，总共有n(n+1)/2个子数组，算法复杂度为O（n^2），这不是最优的解法。
我们换一种思路，考虑到列表中每个元素都可能作为最后一个元素组成一个连续子序列，我们求出规模更小的子序列的最大和，然后由这些子问题序列的解算出问题的解。这其实就是用动态规划思想求解的。
假设f(i)是以第i个字符结尾时，即a_0, a_1,a_2,..,a_i，最大的连续子序列和。f(i)由f(i-1)转化而来，有两种情况
当f[i-1]<0时，f(i)=a[i]，即a[i]作为一个新的子段
当f[i-1]>=0时，f(i)=a[i]+f(i-1)，即最大连续子段一直连续到a[i]
所以递推方程为
f(i)=max(a[i],a[i]+f(i-1))
然后求出max(f(i))就可以了，
def findgreatsumofsublist(alist):
l=r=0
if not isinstance(alist,list):
return False
cursum=[None]*len(alist)
cursum[0]=alist[0]
greatestsum=cursum[0]
for i in range(1,len(alist)):
cursum[i]=max(alist[i]+cursum[i-1],alist[i])
#cursum[i]往前推，直到下标为0或遇到一个负数
maxsum=max(cursum)
r=i=len(cursum)-1
l=0
while i>=0:
if cursum[i]!=maxsum:
i-=1
else:
r=i
break
j=r
while j>=0:
if j==0 or cursum[j-1]<0:
l=j
break
else:
j-=1
return cursum,l,r
测试用例
>>>findgreatsumofsublist([1,2,6,-3,1,-3,15])
([1, 3, 9, 6, 7, 4, 19],0, 6)
>>>findgreatsumofsublist([-1,-2,-3,5])
([-1, -2, -3, 5], 3, 3)
>>>findgreatsumofsublist([-1,-2,6,7,-6,5])
([-1, -2, 6, 13, 7, 12],2, 3)
>>>
>>>findgreatsumofsublist([-1,-2,-3,-2])
([-1, -2, -3, -2], 0, 0)
>>>findgreatsumofsublist([-1,4,-2])
([-1, 4, 2], 1, 1)
