寻找由正数数组构成的最大子序列的算法。注意：不允许相邻元素。

Question

寻找由正数数组构成的最大子序列的算法。注意：不允许相邻元素。

16

例如，给定

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

显然，max(oddIndexSum,evenIndexSum) 并不能起作用。

我面临的主要问题是我无法想出一个元素的选择标准。鉴别标准是微不足道的，只要有选择标准就能确定。

标准的最大子序列算法似乎不适用于这里。我尝试了动态规划方法，但也无法得出结果。我唯一能想到的方法是使用遗传算法。

你会如何解决这个问题呢？

- sundeep

你的问题中隐含的K=3是常量还是变量？ - ShuggyCoUk

1

@ShuggyCoUk: 你是指子序列的长度吗？那是一个变量。 - sundeep

贪心算法也并非在所有情况下都适用。叹气 - JB King

这是我几周前参加期中考试时遇到的一个问题。我使用了贪心算法。我听说动态规划方法也可以解决这个问题。 - Jay Conrod

13个回答

6

克里斯的答案在列表[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...]

这个算法的时间复杂度与朴素的斐波那契函数相同，并且如果你关心效率而不仅仅是得到正确答案，它应该会对一些相同的优化（例如记忆化）产生影响。-- 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]

请注意，我们刚才手动完成的工作，现代语言的好编译器应该能够通过尾递归、记忆化等技术来实现。希望这已经足够清晰了。-- MarkusQ

时间复杂度为O(n)。

- MarkusQ

1

J.F. Sebastian -- 上面的算法是带有记忆功能的线性算法（需要O(n)的空间）。我没有将其详细写出，因为：a）许多现代编程语言都内置了该功能，b）这会使代码变得混乱而晦涩。 - MarkusQ

我尝试为您的算法想出智能记忆化（时间复杂度为O(N)），但失败了。显然我不够聪明 :) 请看@mattiast的答案。他的记忆化技术（动态规划）仅适用于最大子序列和，而不适用于子序列。 - jfs

@J.F.Sebastian -- 关键在于使用类似Lisp的(cons item list)操作向列表中添加元素是常数时间复杂度（就像添加标量一样），而不是O(n)。 - MarkusQ

@Markus@: 毫无疑问，OP的问题可以在O(N)时间内得到答案。正如@sth所证明的那样。问题是：我们是否可以将其称为初始递归算法的智能记忆化。我不知道你最后的算法（含布尔数组）是否有效（很可能有效），但这并不是记忆化。 - jfs

@J.F. Sebastian - 我所做的只是将伪功能代码展开为Algol家族低级别，以帮助您了解发生了什么。如果您仔细查看它，您会发现中间版本只是第一个版本的扩展，后来的版本逐个块对应于中间版本。 - MarkusQ

显示剩余10条评论

3

find_max(int t, int n)
{

     if(t>=n)
       return 0;
     int sum =0, max_sum =0;
     for(int i=t; i<n; ++i)
     {
       sum = sum + A[i];
       for(int j=i+2; j<n; ++j)
          sum = sum + find_max(A[j], n);
       if(sum > max_sum)
          max_sum = sum;
     }
     return max_sum;

}

以上是一种递归解决方案，尚未编译。很容易看到重复的部分并将其转换为DP。很快会发布这个解决方案。

- jwookie

1

这里是使用动态规划完成的答案，使用了与MarkusQ相同的基本概念。我只计算总和，而不是实际序列，可以通过对此代码示例进行简单修改来生成序列。我很惊讶还没有人提到这一点，因为动态规划似乎比递归+记忆化更好！

int maxSeqSum(int *arr, int size) {
  int i, a, b, c;
  b = arr[0];
  a = (arr[1] > arr[0]) ? arr[1]: arr[0];
  for(i=2;i<size;i++) {
    c = (a > (b + arr[i]))? a : (b + arr[i]);
    b = a;
    a = c;
  }
  return a;
}

- vinutheraj

1

一个奇怪的Prolog式伪代码中的递归答案：

maxSum([]) = 0
maxSum([x]) = x
maxSum(A) = max(A[0] + maxSum(A[2..n]),
                A[1] + maxSum(A[3..n]))

在处理超出范围的索引时要适当处理。

编辑：这可以简化为MarcusQ更好的答案：

maxSum([]) = 0
maxSum(A) = max(A[0] + maxSum(A[2..n]), maxSum(A[1..n]))

编辑： 这里有一个版本，它返回实际的子序列而不仅仅是它们的总和。它挑战了我自己编写的伪Prolog-C Chimera的极限，所以我现在就停止。

maxSub([]) = []
maxSub(A) = sub1 = [A[0]] + maxSub(A[2..n])
            sub2 = maxSub(A[1..n])
            return sum(sub1) > sum(sub2) ? sub1 : sub2

- Bennett McElwee

OP 询问的是最大子序列，而不仅仅是其总和。 - jfs

是的，问题的标题是这样说的，但我从实际问题中推断出OP只对总和感兴趣。将此算法扩展为返回子序列及其总和也很简单，但看起来不太美观。 - Bennett McElwee

如果 [] 在伪Prolog-C中不表示链表，则如果涉及创建新子序列，则 [A[0]] + maxSub(A[2..n]) 是O(N)操作（否则算法将无法工作）。 - jfs

一切都应该具有值语义，因此[] + []返回一个新的数组（列表，或其他）。伪Prolog-C伪代码中效率可能不是考虑因素。我试图用简短明了的方式呈现算法，但也许我没有成功。 - Bennett McElwee

我更喜欢使用可执行的伪代码来交流算法，但可能只是我比较奇怪。在这个问题中，除了我的答案之外，只有1个其他答案包含可执行示例。 - jfs

1

@MarkusQ的答案作为Python的一行代码（根据@recursive在评论中的建议进行修改）：

f = lambda L: L and max([L[0]] + f(L[2:]), f(L[1:]), key=sum)

例子：

>>> f([1,51,3,1,100,199,3])
[51, 1, 199]

这种方法效率低下，但可以用于测试更快的解决方案。

在Emacs Lisp中相同的代码

(defun maxsubseq (L)
  "Based on MarkusQ's and sth's answers."
  (if (not L) L
    (let ((incl (cons (car L) (maxsubseq (cddr L))))
          (excl (maxsubseq (cdr L))))
      (if (> (sum incl) (sum excl)) incl excl))))

(defun sum (L) (apply '+ L))

迭代版本（如果有尾递归，则为O（N））

它基于@sth's answer：

(defun maxsubseq-iter-impl (L excl incl)
  (let ((next (if (> (car excl) (car incl)) excl incl)) (x (car L)))
    (if (not L) (cdr next)
      (maxsubseq-iter-impl (cdr L) next
                           (cons (+ x (car excl)) (cons x (cdr excl)))))))
(defun maxsubseq-iter (L) (reverse (maxsubseq-iter-impl L '(0) '(0))))

例子：

(require 'cl)
(loop for f in '(maxsubseq maxsubseq-iter) 
      collect (loop for L in '((1 51 3 1 100 199 3) (9 10 9)) 
      collect (f L)))

输出：

(((51 1 199) (9 9)) ((51 1 199) (9 9)))

- J.F. Sebastian

稍微简短一点的 f = lambda L: L and max([L[0]] + f(L[2:]), f(L[1:]), key=sum) - recursive

0

为避免递归，我们可以从后往前处理，

即）对于数组A [1.。n] ->

     maxSum(A,n): for all n

         if n=0, maxSum = 0 else
         if n=1, maxSum=A[1] else
                maxSum = max(A[n] + maxSum(A,n-2), maxSum(A,n-1))

为了避免计算Max(A,n-2)，同时扩展maxSum(A,n-1)，可以将其存储和计算。这就是为什么我要求反转的原因。即) maxSum(A,n-1) = max(A[n-1]+ maxSum(A,n-3), maxSum(A,n-2))，其中Max(A,n-2)已经得到，无需重新计算。换句话说，使用上述公式计算从1到n的所有n的maxSum(A,n)，以避免重新计算。

例如) n=2，maxSum = max(A[1]+maxSum(A,0), maxSum(A,1)) 例如) n=3，maxSum = max(A[2]+maxSum(A,2), maxSum(A,2))等等，直到达到最后一个n。这将是o(n)。

- lakshmanaraj

我们可以在计算maxsum(A,n-1)之前存储MaxSum(A,n-2)的伪代码，并且我们可以将其带到O(n)。 - lakshmanaraj

0

我们可以使用一个辅助数组B[0..n-1]，其中B[i]是元素A[0..i]和C[0..n-1]的最大和，其中C[i]是布尔值，指示A[i]是否在最大和子序列中:

B[0]=max(A[0],0); C[0]=(A[0]>0)
B[1]=max(B[0],A[1]); C[1]=(A[1]>B[0])
for i in [2..n-1]
  if A[i]+B[i-2] > B[i-1]
      C[i]=True
      B[i]=A[i]+B[i-2]
  else
      C[i]=False
      B[i]=B[i-1]
mssq=[]
i=n-1
while i>=0
  if C[i]
    push(A[i],mssq)
    i=i-2
  else
    i=i-1
return mssq

这显然可以在O(n)的时间和空间内工作。实际上，这与MarcusQ的解决方案相同，只是反转并进行了优化。

- mattiast

问题是关于最大子序列，而不是它的总和。如果您想保持O(N)的时间复杂度，这并不是一个微不足道的更改。 - jfs

考虑这个序列 [5 4 3 4 5 4 3 4]，现在最大和是17。可以使用 [5 4 4 4] 或 [5 3 5 4] 来形成。但是使用您的算法，我们只能得到 [5 4 4 4] 而不能得到其他组合。有什么想法如何改变它？ - Dinesh Gowda

0

编辑：这实际上是另一个帖子的重复，但在发布后我没有意识到。

假设您不需要跟踪哪些项目对最终总和有贡献，您可以在常量空间和线性时间内完成此操作。

伪代码：

sum_excluded_last_item= 0
sum_included_last_item= 0

for each item in list
    if (item>0)
        last_sum_excluded_last_item= sum_excluded_last_item
        sum_excluded_last_item= max(sum_included_last_item, sum_excluded_last_item + item)
        sum_included_last_item= last_sum_excluded_last_item + item
    else
        sum_excluded_last_item= max(sum_excluded_last_item, sum_included_last_item)
        sum_included_last_item= sum_excluded_last_item

max_sum= max(sum_excluded_last_item, sum_included_last_item)

获取实际列表是留给读者的练习。如果您添加更多评论，我也可以帮忙。但这应该从算法中很明显。

- MSN

0

max(oddIndexSum, evenIndexSum) 不起作用。

对于你提供的示例，它起作用-但是，如果你有像这样的东西：A = [1, 51, 3, 2, 41, 23, 20] ，你可以有51 + 2 + 23 = 76 ，或者你可以有51 + 41 + 20 = 112 ，显然更大，也避免相邻元素。这是你要找的吗？

- Andy Mikula

我应该说max（oddIndexSum，evenIndexSum）并不适用于所有情况。我的错... - sundeep

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sth · Accepted Answer

如果您保持两个状态，可以逐步构建最大子序列：

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

如果您想在列表中包含负元素，就需要添加一些条件判断。

相同 -- 更少的代码行数

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

寻找由正数数组构成的最大子序列的算法。注意：不允许相邻元素。

相同 -- 更少的代码行数

同样 -- 消除sum()

总运行时间为O(n)的版本：

在Emacs Lisp中相同的代码

迭代版本（如果有尾递归，则为O（N））

例子：

同样 -- 消除`sum()`