python - 所选值的总最大值

Question

问题:

Given an array of values [a0,a1,a2,..,an]

• Choose values ​​according to the following rules:

  • Only one value can be taken at a turn.

  • If this time already chose the k-th value in array, the next turn can only choose value from k + 1 to n-1.

  • At odd turn ( turn 1, turn 3, ...). Choose any arbitrary values.

  • At even turn ( turn 2, turn 4, ...). Choose a value with the same value as the previous one.

Find and Print The total maximum value of the values that I can choose

示例:

With a=[2,5,2,6].

• Turn 1, choose 2.

• Turn 2, choose 2.

• Turn 3, choose 6.

  • The total maximum values is 10

With a=[6,11,14,0,10,1,11,7,7,11,11,14,14,13,9,0,12,9,11,3].

• The total maximum values is 115

我的代码:

def firstpair(a):
    for i in range(len(a)):
        for j in range(i+1,len(a)):
            if a[i]==a[j]: 
                return [i,j]
    return []
def chooseValues(a):
    s = firstpair(a)
    if len(s)==0: 
        if len(a)==0: return 0
        else: return max(a)
    if s[0]==0: x=0
    else: 
        x = max(a[:s[0]])
    y = a[s[0]]+a[s[1]]+chooseValues(a[s[1]+1:])
    z = chooseValues(a[s[0]+1:])
    return max(x,y,z)

我可以降低上述解决方案的空间复杂度吗？

Answer 1

我认为你可以通过向后进行 n 空间和时间复杂度来做到这一点:

def max_value(items):
    best = [0 for _ in items] + [0]
    last_seen = {}

    for i in reversed(xrange(len(items))):
        curr = items[i]
        pair = last_seen.get(curr)
        if pair is None:
            choose_this = curr
        else:
            choose_this = curr * 2 + best[pair + 1]
        best[i] = max(choose_this, best[i + 1])
        last_seen[curr] = i
    return best[0]

如果你想让它复杂一点，你可以通过组合 last_seen 和 best 以更少的存储空间(与唯一值成比例)来做到这一点:

def max_value(items):
    best_rest = {None: 0}
    best_max = 0

    for i in reversed(range(len(items))):
        curr = items[i]
        choose_this = curr * 2 + best_rest.get(curr, -curr)
        best_rest[curr] = choose_rest = best_max
        best_max = max(choose_this, choose_rest)
    return best_max

无论哪种情况:

assert max_value([6, 11, 14, 0, 10, 1, 11, 7, 7, 11, 11, 14, 14, 13, 9, 0, 12, 9, 11, 3]) == 115
assert max_value([2, 5, 2, 6]) == 10