带交替符号的不相交子阵

Question

我想找到一个算法来找到最大不相交的子数组与交替符号（不一定连续），例如在（2，-3，4.，5，-4，3，-3，5，-2，1）它返回7是最大和，子数组是（5，-3，5）

我用dp做了这样的尝试：

    A=[2,-3,4,5,-4,3,-3,5,-2,1]

    m = A[0]
    flag = A[0]    #flag has the same sign of the previously taken element
    maximum = m    #temporary maxsum

    for i in range(1,10):
        if A[i]>0 and flag<0 or A[i]<0 and flag>0: #i look only for alternate signs
             m = max(m ,A[i]+m)
             if m > maximum:
                   flag = -flag
                    maximum = m
             else:
                   if A[i]>maximum:
                   maximum=A[i]
                   flag=-flag


     print(maximum)

结果是7，但这只是巧合

为了正确比较每个可能的子数组，我应该使用另一个For nested吗？你知道吗

Answer 1

A=[2,-3,4,5,-4,3,-3,5,-2,1]
dp = [[([], 0), ([], 0)]]
for i, x in enumerate(A):
    curr = list(dp[-1])
    if x < 0 and curr[0][1] + x > curr[1][1]:
        curr[1] = (curr[0][0] + [i], curr[0][1] + x)
    elif x > 0 and curr[1][1] + x > curr[0][1]:
        curr[0] = (curr[1][0] + [i], curr[1][1] + x)
    dp.append(curr)

print dp[-1][0]

这将打印一个元组，其中包含要获取的元素的索引和最大和。你知道吗

dp中的每个元素表示列表中下一个数字需要为正（第一个元素）和下一个数字需要为负（第二个元素）的情况下的最佳解决方案。在每一个最好的解决方案中，我们都会列出一个索引列表，以达到该点，以及最大和。答案总是来自dp中的最后一个元素，其中最近的数字是正数。你知道吗

如果不需要跟踪使用的元素：

A=[2,-3,4,5,-4,3,-3,5,-2,1]
dp = [[0, 0]]
for i, x in enumerate(A):
    curr = list(dp[-1])
    if x < 0 and curr[0] + x > curr[1]:
        curr[1] = curr[0] + x
    elif x > 0 and curr[1] + x > curr[0]:
        curr[0] = curr[1] + x
    dp.append(curr)

print dp[-1][0]