Найти индекс подмассива с минимальной суммой

Question

Дан массив длины n с целыми числами (может быть отрицательным или положительным).Найдите начальный и конечный индексы подмассива с минимально возможной суммой.

Answer 1

Поскольку вы указали, что речь идет об алгоритме Каданеса, легко найти множество ссылок на него. GeeksForGeeks: наименьшая сумма непрерывных подмассивов любезно объясняет алгоритм и предоставляет реализации на нескольких языках.

Основываясь на коде python со страницы, я его пересмотрелвозвращать индексы начала / конца, а не суммарное значение.Идея состоит в том, чтобы сохранить индексы диапазона вместе со значением суммы.

import sys

def smallestSumSubarr(arr, n):
    min_ending_here = sys.maxint
    min_so_far = sys.maxint
    min_so_far_range = (-1, 0) # save indices

    for i in range(n):
        if (min_ending_here > 0):
            min_ending_here = arr[i]
            min_ending_here_range = (i, i) # start over
        else:
            min_ending_here += arr[i]
            min_ending_here_range = (min_so_far_range[0], i) # extend the range

        if min_so_far > min_ending_here: # update both value and range
            min_so_far = min_ending_here
            min_so_far_range = min_ending_here_range

    return min_so_far_range # return range instead of value


# Usage
arr = [3, -4, 2, -3, -1, 7, -5]
n = len(arr)
print "Smallest sum range(inclusive): ", smallestSumSubarr(arr, n)

На STDOUT вы увидите

Smallest sum range(inclusive):  (1, 4)