Как получить стартовый индекс для максимальной суммы подмассива

Question

Я использую следующую программу, чтобы найти максимальную сумму и индексы суммы. Я могу получить правильный индекс, но не могу найти правильный индекс.

def max_sum_new(a):
max_current = max_global = a[0]
r_index = 0
for i in range(1, len(a)):
    max_current = max(a[i], max_current+a[i])

    if max_current > max_global:
        max_global = max_current
        r_index = i

return (max_global, r_index)

#Driver Code:
my_arr = [-2, 3, 2, -1]
print(max_sum_new(my_arr))

я получаю

(5, 2)

что ожидается, но я также хочу получить начальный индекс, который в этом случае должен быть 1

так что я ожидаю

(5, 1, 2)

Есть ли способ получить стартовый индекс здесь? Как мне поставить переменную для записи индекса начала?

Answer 1

Вам просто нужно применить ту же логику, что и с r_index, Всякий раз, когда вы меняете max_current, это когда начало максимального подмассива изменяется. В конце концов это выглядит так

max_current = max_global = a[0]
r_index = 0
left_index = 0
for i in range(1, len(a)):
    if a[i] > max_current + a[i]:
        # Here is where your start index changes
        left_index = i
        max_current = a[i]
    else:
        max_current = a[i] + max_current

    if max_current > max_global:
        max_global = max_current
        r_index = i

print(max_global, left_index, r_index)