1. 首页
  2. 问题
  3. 寻找正数数组最大子序列的算法。捕获：不允许相邻元素
一尘不染

寻找正数数组最大子序列的算法。捕获：不允许相邻元素

algorithm

例如，给定

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

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

我遇到的主要问题是我无法提出元素的选择标准。给定选择标准，拒绝标准是微不足道的。

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

您将如何处理？


阅读 197

收藏
2020-07-28

共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])

如果您还希望列表中包含否定元素，则必须添加一些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
2020-07-28