python 优化原始列表的列表中的最大和的性能

wvmv3b1j 于 2023-01-01 发布在 Python

关注(0)|答案(2)|浏览(138)

我正在写我的python，做代码战。描述如下：
最大和子数组问题在于找到整数数组或列表中连续子序列的最大和：
max_sequence（[-2，1，-3，4，-1，2，1，-5，4]）应该为6：[四、一、二、一]
简单的情况是列表只由正数组成，最大和是整个数组的和。如果列表只由负数组成，则返回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要求你通过大量的测试，并且测试超时。
在讨论中，很多人都有和我一样的问题，其中一个答案特别切中了问题的根源，也就是我在这里要问的问题（见下面的评论）：
你的代码没有优化到可以处理更长的数组，虽然你的代码可能可以工作，但是解决更难的问题需要太长的时间，所以超时了。这个问题和任何优化问题一样多。所以你需要找到一种方法来优化你的解决方案
这对我来说是非常正确的！在这个数据结构中，我做错了什么？我如何改进它？我目前对最昂贵的计算的猜测是：
1.循环中循环（对于范围i中的i....对于范围i中的j）
1.列表。追加（arr[j：i]）
有什么建议吗？如何提高这里的性能？我在思考一般的数据结构和学习，就像我在解决这个具体的问题一样。谢谢！

python

来源：https://stackoverflow.com/questions/74970542/optimizing-performance-for-max-sum-in-list-of-lists-for-original-list

2条答案

按热度按时间

hgqdbh6s1#

参考：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

赞(0）回复(0）举报 2023-01-01

x6492ojm2#

类似的想法与较早的职位，但它试图 * 保释 * 更早时，击中 * 边缘情况 *：时间复杂度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

赞(0）回复(0）举报 2023-01-01

我来回答

python 优化原始列表的列表中的最大和的性能

2条答案

相关问题

热门标签

最新问答