如何打印具有非相邻元素的数组的最大和子序列？

Question

我有代码来找到可以用数组的非相邻元素形成的最大总和。如何打印有助于总和的元素？

def find_max_sum(arr): 
  incl = 0
  excl = 0
  for i in range(len(arr)): 
    if excl>incl:
      new_excl = excl
    else:
      new_excl = incl
    incl = excl + arr[i]
    excl = new_excl
  return (excl if excl>incl else incl) 

Answer 1

我认为你正在尝试实现Kadane的算法但不是很正确。 Kadane的算法应如下所示：

def kadane(arr):
    maxseen = 0
    window = 0
    for i in range(len(arr)):
        window = max(arr[i], window+arr[i])
        maxseen = max(window, maxseen)
    return maxseen

该算法将给出总和（min为0，对于arr的空子阵列）但不是子阵列。所以你只需要记住如何提出解决方案：

def kadane(arr):
    if not arr:
        return []  # corner case
    maxi = wini = maxj = 0
    maxseen = 0
    winmax = 0  # max sum of window ends at winj
    for winj in range(len(arr)):
        if winmax + arr[winj] < arr[winj]:
            winmax = arr[winj]
            wini = winj
        else:
            winmax += arr[winj]
        if winmax > maxseen:
            maxi = wini
            maxj = winj
    return arr[maxi:maxj+1]