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

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) 

标签： pythondynamic-programmingarray-algorithms

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

该算法将为您提供总和（对于 的空子数组，最小值为 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]