求数组中非连续所有格元素最大和的逻辑实现

Question

它们是一个包含正整数和负整数的数组 假设：1,2，-1,3,5,1，-4,2,7 现在我要找到所有组合的最大和

组合应该是这样的

1.主集合中没有连续的元素
2.元素应为正

起初，我想通过将它划分为偶数和概率来实现这一点，但实际上这并不能解决问题

 ods=[]
 evns=[]
 ok=0;
 ek=1;
 for x in range(n):
            print(str(x)+"-"+str(ok)+"-"+str(ek))
            if x == ok and tkts[x]>0:
                ods.append(tkts[x])
                ok+=2
            elif x == ok and tkts[x] <= 0:
                ok+=1

            if x == ek and tkts[x]>0:
                evns.append(tkts[x])
                ek+=2
            elif x == ek and tkts[x] <= 0:
                ek+=1 

有什么逻辑可以请一个人帮忙

Answer 1

你可以用DP。递归思想如下

get_max(index):
    max = 0
    for i from index+2 to len:
        if(array[i] > 0)
            v = get_max(i)
            if (v > max) max = v
    return array[index]+max
get_max(0)

如果我们记住

x = [1,2,-1,3,5,1,-4,2,7]
dp = [0]*len(x)
ret = 0
for i in range(len(x)-3, -1, -1):
    max = 0
    for j in range(i+2, len(x)):
        if x[j] > 0 and dp[j]>max: max = dp[j]
    if x[i] > 0:
        dp[i] = max + x[i]
        if ret < dp[i]: ret = dp[i]

（我没有测试这个代码，这只是为了这个想法）