找到正数数组的最大子序列的算法.捕获:不允许相邻元素

Question

例如,给定

A = [1,51,3,1,100,199,3], maxSum = 51 + 1 + 199 = 251.

显然max(oddIndexSum,evenIndexSum)也不能正常工作.

我遇到的主要问题是我无法为元素提出选择标准.在给定选择标准的情况下,拒绝标准是微不足道的.

标准最大子序列算法似乎不适用于此处.我尝试过一种动态编程方法,但也无法想出.我能想到的唯一方法是使用遗传算法的方法.

你会怎么做？

Answer 1

如果保持两种状态,则可以逐步构建最大子序列:

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

好吧,我们来优化吧......

总运行时间为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

Answer 2

克里斯的答案在名单[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).