算法找到正数的阵列的最大序列。抓：不允许相邻的元素 [英] 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屋！