Как написать в Python код нахождения максимальной суммы подмассива, чтобы помимо суммы, выводились границы оптимального подмассива?

Если массив искать по алгоритму Кадане, тогда нужно добавить пару строк для записи границ. Саму функцию взял из статьи по ссылке и отредактировал.

from sys import maxsize 


def max_sub_array_sum(a,size): 
    max_so_far = -maxsize - 1
    max_ending_here = 0
    borders = [0, 0]

    for i in range(0, size): 
        max_ending_here = max_ending_here + a[i] 
        if (max_so_far < max_ending_here):
            borders = [borders[1], i]
            max_so_far = max_ending_here 

        if max_ending_here < 0: 
            max_ending_here = 0   
    return max_so_far, borders

Добавил borders. Когда мы находим сумму больше предыдущей обновляем границы. Правый край прошлой границы становится началом новой.

Теперь проверим на том же примере из статьи:

a = [-2, -3, 4, -1, -2, 1, 5, -3] 
print("Maximum contiguous sum is", max_sub_array_sum(a,len(a)))

Вывод: Maximum contiguous sum is (7, [2, 6])