所选值的总最大值。
所选值的总最大值。
提问于 2019-12-03 18:42:59
问题:
给出了一个值数组-- a0、a1、a2、..
- 根据以下规则选择值：
- 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.
查找并打印我可以选择的值的总最大值。
示例:
和a=2,5,2,6。
- 转1，选择2.
- 转2，选择2.
- 转3，选择6.
- The total maximum values is 10
用a=6,11,14,0,10,1,11,7,7,11,11,14,14,13,9,0,12,9,11,3.
- 总最大值为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)我可以降低上述解决方案的空间复杂度吗？
回答 2
Stack Overflow用户
发布于 2019-12-04 00:03:31
我认为您可以使用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]) == 10Stack Overflow用户
发布于 2019-12-03 23:39:48
这里有一种思考的方法。让f(i, parity)代表在具有奇偶校验( parity )的步骤中选择ith元素时所达到的最大值。然后：
f(i, even) = A[i] + max(f(j, odd)) // requires O(1) storage
where j < i and A[j] == A[i]
f(i, odd) = A[i] + max(f(j, even)) // requires O(num_unique_Ai) storage
where j < idef f(A):
max_f_j_even = -float("inf")
max_f_j_odd = {A[0]: A[0]}
best = -float("inf")
for i in range(1, len(A)):
# Even turn
new_max_f_j_even = None
if A[i] in max_f_j_odd:
new_max_f_j_even = max(max_f_j_even, A[i] + max_f_j_odd[A[i]])
# Odd turn
else:
# A[i] is a first turn
max_f_j_odd[A[i]] = A[i]
# A[i] is a later odd turn
max_f_j_odd[A[i]] = max(max_f_j_odd[A[i]], A[i] + max_f_j_even)
if new_max_f_j_even != None:
max_f_j_even = new_max_f_j_even
best = max(best, max_f_j_even, max_f_j_odd[A[i]])
return best
A = [2,5,2,6]
print(f(A)) # 10
A = [6,11,14,0,10,1,11,7,7,11,11,14,14,13,9,0,12,9,11,3]
print(f(A)) # 115页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59163445
复制相关文章
相似问题
腾讯云开发者
