Вам дан массив $$$a$$$ состоящий из $$$n$$$ целых чисел. Красота массива – это максимальная сумма какого-то последовательного подотрезка этого массива (этот подотрезок может быть пустым). Например красота массива [10, -5, 10, -4, 1] равна 15, а красота массива [-3, -5, -1] равна 0.
Вы можете выбрать не более одного последовательного подотрезка массива $$$a$$$ и домножить все элементы этого подотрезка на $$$x$$$. Вы хотите максимизировать красоту массива после применения такой операции.
Первая строка содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 3 \cdot 10^5, -100 \le x \le 100$$$) — длина массива $$$a$$$ и число $$$x$$$ соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — сам массив $$$a$$$.
Выведите одно число — максимальную красоту массива $$$a$$$ после не более одного домножения непрерывного подотрезка этого массива на $$$x$$$.
5 -2 -3 8 -2 1 -6
22
12 -3 1 3 3 7 1 3 3 7 1 3 3 7
42
5 10 -1 -2 -3 -4 -5
0
В первом тестовом примере нужно домножить подотрезок [-2, 1, -6], после этого массив примет вид [-3, 8, 4, -2, 12] с красотой 22 ([-3, 8, 4, -2, 12]).
Во втором примере нам не нужно домножать какой-либо подотрезок массива вообще.
В третьем тестовом примере независимо от того, какой подотрезок мы домножим, красота массива будет равна 0.
Название |
---|