题目描述:
给你一个整数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)