寻找正数数组最大子序列的算法。捕获：不允许相邻元素
问题内容：
例如，给定
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])
如果您还希望列表中包含否定元素，则必须添加一些if。
相同-较小的行
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
好吧，让我们对其进行优化…
总运行时间为O（n）的版本：
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
