我正在开发我的python，进行代码战争。描述如下：
最大和子数组问题在于找到数组或整数列表中相邻子序列的最大和：
max_sequence([-2，1，-3,4，-1，2,1，-5，4])应为6:[4，-1，2，1]
简单的情况是，列表仅由正数组成，最大和是整个数组的和。如果列表仅由负数组成，则返回0。
空列表被认为具有零个最大和。请注意，空列表或数组也是一个有效的子列表/子数组。
太棒了！完成！这是我的代码，它通过了测试：
def max_sequence(arr):
sums = []
lists = [[]]
for i in range(len(arr) + 1):
for j in range(i):
lists.append(arr[j: i])
for i in lists:
sums.append(sum(i))
return max(sums)
然而，对于提交，codewars要求您通过一组更大的测试，并且对于更大的集合，测试会超时。
在讨论中，许多人都和我有同样的问题。有一个答案特别触及问题的根源，这就是我在这里问的(见下面的评论)：
您的代码不会选择使用更长的数组，虽然您的代码可能会工作，但解决更难的问题需要很长时间，因此超时。这个问题和任何问题一样都是一个优化问题。因此，您需要找到一种方法来优化您的解决方案
这对我来说是真的！我在做什么；错误的"；在这个数据结构中，我该如何改进它？我目前对最昂贵计算的猜测是：
- 循环中的循环(对于范围i……对于范围i中的j)
- lists.append(arr[j:i])
有什么建议吗？如何在这里提高性能？我对一般数据结构和学习的思考与解决这个特定问题的思考一样多。非常感谢。
与之前的帖子有类似的想法，但当遇到边缘情况时，它试图更早地退出：(它仍然实现了O(n))
def maxSequence(arr):
if not arr: return 0 # check if it's empty list
if max(arr) < 0: return 0 # check if all negatives
maxx,curr= 0, 0
for x in arr:
curr += x
if curr < 0:
curr = 0
if curr> maxx:
maxx = curr
return maxx
参考：https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane算法
你可以使用Kadane的算法。其思想是不断向curr添加元素，得到curr和num的最大值。当子数组的和为正时，它会继续。当子阵列之和为负时，它将放弃负子阵列。
您可以使用以下代码来考虑此示例：[-1,1000,-2]。最初，curr = -1。由于它是负的，curr放弃-1，得到1000的值。最后，由于1000大于998，因此返回1000作为答案。
这只具有O(n)的时间复杂性，而不是具有O(n^3)的暴力方法。
def max_sequence(arr):
if not arr or max(arr) < 0:
return 0
curr = max_sub = arr[0]
for num in arr[1:]:
curr = max(num, curr + num)
max_sub = max(max_sub, curr)
return max_sub