例如,给定
A = [1,51,3,1,100,199,3], maxSum = 51 + 1 + 199 = 251.
显然max(oddIndexSum,evenIndexSum)也不能正常工作.
我遇到的主要问题是我无法为元素提出选择标准.在给定选择标准的情况下,拒绝标准是微不足道的.
标准最大子序列算法似乎不适用于此处.我尝试过一种动态编程方法,但也无法想出.我能想到的唯一方法是使用遗传算法的方法.
你会怎么做？
如果保持两种状态,则可以逐步构建最大子序列:
def maxsubseq(seq):
# maximal sequence including the previous item
incl = []
# maximal sequence not including the previous item
excl = []
for i in seq:
# current max excluding i
if sum(incl) > sum(excl):
excl_new = incl
else:
excl_new = excl
# current max including i
incl = excl + [i]
excl = excl_new
if sum(incl) > sum(excl):
return incl
else:
return excl
print maxsubseq([1,4,6,3,5,7,32,2,34,34,5])
如果您还希望在列表中包含负面元素,则必须添加一些ifs.
def maxsubseq2(iterable):
incl = [] # maximal sequence including the previous item
excl = [] # maximal sequence not including the previous item
for x in iterable:
# current max excluding x
excl_new = incl if sum(incl) > sum(excl) else excl
# current max including x
incl = excl + [x]
excl = excl_new
return incl if sum(incl) > sum(excl) else excl
sum()def maxsubseq3(iterable):
incl = [] # maximal sequence including the previous item
excl = [] # maximal sequence not including the previous item
incl_sum, excl_sum = 0, 0
for x in iterable:
# current max excluding x
if incl_sum > excl_sum:
# swap incl, excl
incl, excl = excl, incl
incl_sum, excl_sum = excl_sum, incl_sum
else:
# copy excl to incl
incl_sum = excl_sum #NOTE: assume `x` is immutable
incl = excl[:] #NOTE: O(N) operation
assert incl is not excl
# current max including x
incl.append(x)
incl_sum += x
return incl if incl_sum > excl_sum else excl
好吧,我们来优化吧......
def maxsubseq4(iterable):
incl = [] # maximal sequence including the previous item
excl = [] # maximal sequence not including the previous item
prefix = [] # common prefix of both sequences
incl_sum, excl_sum = 0, 0
for x in iterable:
if incl_sum >= excl_sum:
# excl <-> incl
excl, incl = incl, excl
excl_sum, incl_sum = incl_sum, excl_sum
else:
# excl is the best start for both variants
prefix.extend(excl) # O(n) in total over all iterations
excl = []
incl = []
incl_sum = excl_sum
incl.append(x)
incl_sum += x
best = incl if incl_sum > excl_sum else excl
return prefix + best # O(n) once
克里斯的答案在名单[9,10,9]上失败,产生10而不是9 + 9 = 18.
乔不太对劲.旅行推销员要求您访问每个城市,而这里没有类似的东西.
一种可能的解决方案是递归解决方案:
function Max_route(A)
if A's length = 1
A[0]
else
maximum of
A[0]+Max_route(A[2...])
Max_route[1...]
这与原始的斐波那契函数具有相同的大O,并且除了简单地得到正确的答案之外,如果您关心效率,则应该产生一些相同的优化(例如,记忆).
- MarkusQ
[编辑] ---
因为有些人似乎没有得到这个,我想解释一下我的意思是什么,以及它为何重要.
您可以将上面的函数包装起来,以便它只计算每个数组的值一次(第一次调用它),并且在后续调用中只返回保存的结果.这将占用O(n)空间,但会在恒定时间内返回.这意味着整个算法将在O(n)时间内返回,优于上面较不杂乱的版本的指数时间.我假设这很好理解.
[第二次编辑] ------------------------------
如果我们将上面的内容扩展一点并将它分开,我们得到:
f [] :- [],0
f [x] :- [x],x
f [a,b] :- if a > b then [a],a else [b],b
f [a,b,t] :-
ft = f t
fbt = f [b|t]
if a + ft.sum > fbt.sum
[a|ft.path],a+ft.sum
else
fbt
我们可以使用大小为n的整数和布尔数组,以及1)数组索引和索引数组赋值,2)整数数学,包括比较,3)if/then/else和4)的操作,展开伪基本一个单一的O(n)循环:
dim max_sum_for_initial[n],next_to_get_max_of_initial[n],use_last_of_initial[n]
max_sum_for_initial[0] = 0
next_to_get_max_of_initial[0] = -1
use_last_of_initial[0] = false
max_sum_for_initial[1] = a[0]
next_to_get_max_of_initial[1] = -1
use_last_of_initial[1] = true
if a[0] > a[1]
max_sum_for_initial[2] = a[0]
next_to_get_max_of_initial[2] = 0
use_last_of_initial[2] = false
else
max_sum_for_initial[2] = a[1]
next_to_get_max_of_initial[1] = -1
use_last_of_initial[2] = true
for i from 3 to n
if a[i]+max_sum_for_initial[i-2] > max_sum_for_initial[i-1]
max_sum_for_initial[i] = a[i]+max_sum_for_initial[i-2]
next_to_get_max_of_initial[i] = i-2
use_last_of_initial[i] = true
else
max_sum_for_initial[i] = max+sum_for_initial[i-1]
next_to_get_max_of_initial[i] = i-1
use_last_of_initial[i] = false
最后,我们可以提取结果(以相反的顺序):
for i = n; i >= 0; i = next_to_get_max_of_initial[i]
if use_last_of_initial[i] then print a[i]
请注意,我们手动执行的操作是现代语言的良好编译器应该能够通过尾递归,memoization等完成的.
我希望这很清楚.
- MarkusQ
这是O(n).
京公网安备 11010802040832号 | 京ICP备19059560号-6 
