Блог

Главная - Вопросы по программированию - Как напечатать подпоследовательность максимальной суммы массива с несмежными элементами?

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

#python #dynamic-programming #array-algorithms

#python #динамическое программирование #массив-алгоритмы

Вопрос:

У меня есть код для нахождения максимальной суммы, которая может быть сформирована из несмежных элементов массива. Как распечатать элементы, которые внесли вклад в сумму?

 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)

Комментарии:

1. пожалуйста, отправьте код, а не изображение кода

2. @adrtam Взгляните на это сейчас.

3. Было бы полезно, если бы у вас был некоторый образец ввода и вывода. Опубликованный вами код, похоже, не соответствует вашему названию.

Ответ №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]