Question

Решить на python Дан массив целых чисел A[N]. Требуется найти непрерывный отрезок массива, сумма элементов которого максимальна. Входные данные В первой строке записано число N (1 ≤ N ≤ 10000). Во второй строке записаны через пробел элементы массива. Выходные данные В первой строке записаны индексы начала и конца искомого отрезка. Во второй строке записана сумма элементов этого отрезка.

Answer 1

n = int(input("Input N: "))

numbers = input("Input numbers: ").split()

print(numbers)

sum = 0

ans = int(numbers[0]);

left = 0

right = 0

pos = -1

for i in range(n):

sum += int(numbers[i])

if sum > ans:

ans = sum

right = i

left = pos + 1

if sum < 0:

sum = 0

pos = i

print("Left:" + str(left + 1), " Right:" + str(right + 1))

print("Answer:" + str(ans));

Answer 2

Для решения этой задачи можно использовать алгоритм Кадана (Kadane's algorithm). Алгоритм Кадана эффективно находит максимальную сумму подмассива (непрерывного отрезка) массива.

Вот Python код, который решает данную задачу:

pythonCopy code
def kadane_algorithm(arr):
    max_so_far = max_ending_here = arr[0]
    start = end = 0
    temp_start = 0

    for i in range(1, len(arr)):
        if arr[i] > max_ending_here + arr[i]:
            max_ending_here = arr[i]
            temp_start = i
        else:
            max_ending_here += arr[i]

        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
            start = temp_start
            end = i

    return start, end, max_so_far


if __name__ == "__main__":
    N = int(input("Введите число N (1 ≤ N ≤ 10000): "))
    A = list(map(int, input("Введите элементы массива через пробел: ").split()))

    start_idx, end_idx, max_sum = kadane_algorithm(A)

    print("Индексы начала и конца искомого отрезка: {} {}".format(start_idx, end_idx))
    print("Сумма элементов этого отрезка: {}".format(max_sum))

Вы можете скопировать этот код в свой Python интерпретатор или среду разработки, и он попросит вас ввести число N и элементы массива A. Затем программа найдет и выведет индексы начала и конца искомого отрезка, а также сумму элементов этого отрезка.