逻辑实现，以查找数组中非连续占有元素的最大总和

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]

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