Как напечатать максимальную сумму подпоследовательности массива с несмежными элементами?

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

Я думаю, что вы пытаетесь реализовать алгоритм Кадане, но не совсем в правильной форме.Алгоритм Кадане должен выглядеть следующим образом:

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]