Покоряем максимальный подмассив с помощью алгоритма divide & conquer
Существует множество способов найти подмассив с максимально возможной суммой среди
n целых чисел. Один из них — использовать алгоритм divide & conquer (разделяй и властвуй). Суть метода заключается в том, чтобы рекурсивно разделять массив на две части, находить максимальный подмассив для левой и правой половин, а также подмассив, который пересекает середину. Затем из этих трёх результатов формируется ответ для текущего массива.Ниже приведён псевдокод алгоритма:
def max_subarray(a):
# Базовые случаи
if len(a) == 0:
return float('-inf'), float('-inf'), float('-inf')
if len(a) == 1:
return a[0], a[0], a[0]
# Разделяем (получаем ответы для левой и правой частей)
ll, lmax, lr = max_subarray(a[:len(a) // 2])
rl, rmax, rr = max_subarray(a[len(a) // 2:])
lsum = sum(a[:len(a) // 2])
rsum = sum(a[len(a) // 2:])
# Получаем 3 числа и возвращаем максимальный префикс, максимальный суффикс и общее максимальное суммарное значение
return conquer(ll, lmax, lr, lsum, rl, rmax, rr, rsum)В данной задаче от вас требуется реализовать часть функции
conquer, где, имея на входе 8 чисел, необходимо вычислить три значения: наилучшую префиксную сумму, наилучшую сумму, пересекающую середину, и наилучшую суффиксную сумму. Эти 8 входных чисел соответствуют следующим величинам:- Лучшая префиксная сумма левого подмассива
- Максимальная сумма левого подмассива
- Лучшая суффиксная сумма левого подмассива
- Сумма всех чисел левого подмассива
- Лучшая префиксная сумма правого подмассива
- Максимальная сумма правого подмассива
- Лучшая суффиксная сумма правого подмассива
- Сумма всех чисел правого подмассива
Вход
В единственной строке ввода содержится 8 целых чисел в описанном выше порядке. Все эти числа не превышают по абсолютному значению.
Выход
Программа должна вывести 3 числа: лучшую префиксную сумму, лучшую сумму, пересекающую середину, и лучшую суффиксную сумму.
Примеры
Вход | Выход |
7 13 9 6 7 9 3 -2 | 13 16 7 |
7 13 9 6 5 25 3 1 | 11 25 10 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB