Skip to content
TheChatArchiveThe Chat Archive
gpt-4-1106-preview· openaiHugging Face Suzhen/CodeChat

Напиши программу, выводящую индексы отрезка максимальной суммы

  1. User

    Напиши программу, выводящую индексы отрезка максимальной суммы

  2. Assistant

    Чтобы найти индексы подмассива с максимальной суммой, вы можете использовать алгоритм Кадана. Этот алгоритм поможет найти максимальную сумму непрерывного подмассива в одномерном массиве целых чисел за время O(n), где n — количество элементов в массиве.

    Ниже представлена реализация алгоритма на языке программирования Python, которая выводит индексы начала и конца подмассива (отрезка) с максимальной суммой:

    def max_subarray_indices(arr):
        max_sum = float('-inf')
        current_sum = 0
        start_index = 0
        end_index = 0
        temp_start_index = 0
        
        for i, number in enumerate(arr):
            current_sum += number
            
            if current_sum > max_sum:
                max_sum = current_sum
                start_index = temp_start_index
                end_index = i
            
            if current_sum < 0:
                current_sum = 0
                temp_start_index = i+1
        
        return (start_index, end_index)
    
    # Пример использования функции
    if __name__ == "__main__":
        arr = [-2, -3, 4, -1, -2, 1, 5, -3]
        start, end = max_subarray_indices(arr)
        print(f"Начальный индекс: {start}, Конечный индекс: {end}")
    

    Здесь функция max_subarray_indices принимает массив arr и возвращает пару индексов start_index и end_index, которые указывают на начало и конец подмассива с максимальной суммой соответственно.

    Обратите внимание, что если в массиве есть несколько подмассивов с одинаковой максимальной суммой, представленный алгоритм вернёт индексы первого найденного такого подмассива.