算法找到正数的阵列的最大序列。抓:不允许相邻的元素 [英] Algorithm to find the maximum subsequence of an array of positive numbers . Catch : No adjacent elements allowed
问题描述
例如,给
A = [1,51,3,1,100,199,3], maxSum = 51 + 1 + 199 = 251.
明确 MAX(oddIndexSum,evenIndexSum)
确实不是工作
主要的问题我已经是我不能拿出一个选择标准的元素。 的拒绝标准是微不足道给出一个选择标准。
The main problem I have is that I can't come up with a selection criterion for an element. A rejection criterion is trivial given a selection criterion.
的标准最大子序列算法似乎没有在这里是适用的。 我已经尝试了动态规划方法,但不能拿出,要么。 我能想出的唯一办法是一个用遗传算法。
The standard maximum sub-sequence algorithm doesn't seem to be applicable here. I have tried a dynamic programming approach, but can't come up with that either. The only approach I could come up with was one that used a genetic algorithm.
你会如何处理这个?
推荐答案
可以,如果你把两个国家建立一个脚印的最大子步:
You can build the maximal subsequence step by step if you keep two states:
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。
If you also want to have negative elements in your lists, you have to add a few 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
相同 - 消除和()
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
还好吧,让我们来优化它...
Allright, let's optimize it...
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
这篇关于算法找到正数的阵列的最大序列。抓:不允许相邻的元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!