Задача 70: Отрезок с максимальной суммой

Условие задачи:

В одномерном массиве, заполненном произвольными целыми числами, за один проход найдите непрерывный кусок, сумма чисел в котором максимальна.

Примечание. Фактически требуется найти такие \(i\) и \(j\) \((i <= j)\), что сумма всех элементов массива от \(a_i\) до \(a_j\) включительно будет максимальна.

Входные данные:

На вход программе сначала подается натуральное \(n <= 10^5\) — количество элементов в массиве. Далее, по одному в строке расположены сами элементы массива — целые числа, по модулю не превосходящие \(3 * 10^4\).

Выходные данные:

Выдайте пару искомых значений индексов. Если таких пар несколько, то \(j\) должно быть минимально возможным, а при равных \(j\) значение \(i\) должно быть максимально возможным.

Решение:

lst = [0] + [int(input()) for i in range(int(input()))]
for v in range(1, len(lst)):
    lst[v] += lst[v - 1]

i = 0
j = 1
lst_min = 0
vsv_i = 0
vsv_j = 1
tmp_s = None

for s in range(1, len(lst)):
    if lst[s - 1] <= lst[lst_min]:
        lst_min = s - 1
    if lst[vsv_j] - lst[vsv_i] < lst[s] - lst[lst_min]:
        vsv_i = lst_min
        vsv_j = s
        
        
print(vsv_i + 1)
print(vsv_j)

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик