python - 在python中查找最大非负子数组

Question

我试图从给定的子数组中查找包含比任何其他子数组最大总和的元素的子数组。

下面的函数有参数作为输入a并且需要返回输出。可以有多个子数组，因为它们的最大和可以相等。该代码似乎没有按预期工作。

def max_sum_subarray(a):
        N, sub_sum, max_sum, subArrays = len(a), 0, 0, {}
        p,q=0,0    #starting and ending indices of a max sub arr

        for i in range(N):
            q=i
            sub_sum+=a[i]

            if(a[i]<0):
                q-=1
                if(sub_sum>=max_sum):
                    if(sub_sum>max_sum):
                        subArrays.clear()
                        subArrays[sub_sum]=[(p,q)]
                    else:
                        subArrays[sub_sum].append((p,q))

                sub_sum=0
                p=i+1

        if(sub_sum>=max_sum):
            if(sub_sum>max_sum):
                subArrays.clear()
                subArrays[sub_sum]=[(p,q)]
            else:
                subArrays[sub_sum].append((p,q))
        return(subArrays[p:q+1])

当我尝试运行输入时

a=[ 1, 2, 5, -7, 2, 5 ]

预期输出是[1, 2, 5]，但它却给出了[2, 5]。谁能用 python 发布解决方案吗？

Answer 1

看来你让这件事变得不必要了。您可以只跟踪到目前为止看到的最大数组以及您当前正在插入的数组 - 您实际上不需要关心其他任何事情。当您达到负数(或数组末尾)时，决定当前是否应该是新的最大值:

def maxSub(a):
    max_so_far = []
    max_sum = 0
    cur = []
    for n in a:
        if n >= 0:
            cur.append(n)
        else:
            cur_sum = sum(cur)
            if cur_sum > max_sum:
                max_sum = cur_sum
                max_so_far = cur
            cur = []

    return max([max_so_far, cur], key = sum)


a=[ 1, 2, 5, -7, 2, 5 ]

maxSub(a)
# [1, 2, 5]

当然itertools.groupby使其成为一句台词:

from itertools import groupby

a=[ 1, 2, 5, -7, 2, 5 ]
max([list(g) for k,g in groupby(a, key=lambda x: x>0) if k == True], key=sum)