Максимальная сумма подмассива с использованием метода «разделяй и властвуй» (Divide & Conquer)

Дан массив из n целых чисел. Используя метод «разделяй и властвуй» (divide & conquer), необходимо найти непрерывный подмассив, сумма значений которого максимальна.

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

В первой строке входных данных содержится целое число n — количество элементов в массиве (1 ≤ n ≤ ).

Во второй строке заданы n целых чисел, разделённых пробелом, которые представляют элементы массива .

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

Программа должна вывести одно целое число — максимально возможную сумму непрерывного подмассива в данном массиве.

Примеры

Пояснение

1. -2 1 -3 4 -1 3 1 -4 -2 → Сумма выделенного подмассива: (4 - 1 + 3 + 1) = 7

2. 1 -2 3 4 -3 1 7 -10 -20 4 → 3 + 4 -3 + 1 + 7 = 12