题目描述：
给你一个整数list L, 如 L=[2,-3,3,50], 求L的一个连续子序列，使其和最大，输出最大子序列的和。 例如，对于L=[2,-3,3,50]， 输出53（分析：很明显，该列表最大连续子序列为[3,50]).
示例：
输入：L = [2, -3, 3, 50]
输出：53
分析：
首先我们来分析一下示例，
53 = 3 + 50
接下来我们开始分析了，要求一个 连续的子序列，使其和最大。怎么办？
首先想到的就是，遍历这个子序列的起点和终点，然后求和，找到最大的和。或者是确定子序列的起点和长度，求和，再求最大值。那么程序的代码可能就是这样的：
1
2
3
4
5
6
7
maxx = 0
for i in range(n+1):
for j in range(n+1):
sums = 0
for k in range(i, j+1):
sums += L[k]
maxx = max(maxx, sums)
上面的代码的时间复杂度可以算出是 O(n3),
当然我们也可以使用前缀和的方式，来优化到 O(n2),例如：不懂前缀和的同学可以百度一下，这个很好理解。
1
2
3
4
5
6
7
for i in range(1, n):
L[i] = L[i] + L[i-1]
maxx = 0
for i in range(n+1):
for j in range(n+1):
maxx = max(maxx, L[j]-L[i])
如果数据量不是很大的时候，这样类似的代码基本上就可以完成了。
我们再思考一下，是不是可以再优化一下。
如果当前序列和 > 0的。往后扩展那就有会比后面的数大。
但是当前序列和 <= 0的，往后面扩展就会比后面的数小。
这个很好理解。假设 : c = a + b
当 a > 0 的时候，一定有 c > b；
当 a <= 0 的时候， 一定有 c <= b;
所以只要当 a <= 0 时，重新开始记录就可以了。这样的话，我们的时间复杂度就是 O(n)
代码：
1
2
3
4
5
6
7
8
9
res = 0
max_res = 0
for item in L:
res += item
if res < 0:
res = 0
max_res = max(res, max_res)
print(max_res)