Чмяяякс на префіксі
Вам даний масив , що складається з цілих чисел. Вам потрібно виконати наступні кроки в заданому порядку:
Вибрати деякий індекс .
Розділити масив на дві частини: та .
Видалити один елемент з обох частин.
Позначимо як суму елементів першої отриманої частини та як суму елементів другої. Вам потрібно знайти максимально можливе значення . Іншими словами, ваше завдання полягає в знаходженні максимально можливої різниці між сумами отриманих частин після виконання цих кроків.
Ви можете вважати, що сума елементів порожнього масиву дорівнює .
Вхідні дані
Перший рядок містить одне ціле число — кількість елементів у масиві .
Другий рядок містить міститься цілих чисел — елементи масиву.
Вихідні дані
У першому та єдиному рядку виведіть одне ціле число — максимально можливу різницю між сумами отриманих частин після виконання таких кроків.
Приклади
Примітка
У першому прикладі, єдиний спосіб розділити масив — взяти , тобто створити два підмасиви та . Оскільки вони обидва складаються з одного елемента, єдиний спосіб видалити один елемент з кожного підмасиву — видалити обидва. Таким чином, підмасиви стають порожніми, їх суми стають , отже відповідь дорівнює .
У другому прикладі є способів виконання операцій:
-> -> результат ;
-> -> результат ;
-> -> ;
-> -> ;
-> -> ;
-> -> ;
-> -> ;
-> -> ;
-> -> ;
-> -> .
Як ми можемо помітити, максимально можливе значення тут дорівнює , яке можна отримати, вибравши та залишивши з першого отриманого підмасиву та з другого.
У третьому прикладі, не має значення, як ми розділимо масив або який елемент ми видалимо з них — сума будь-якого з отриманих підмасивів завжди буде , так само як і різниця між ними.
Оцінювання
( бали): ;
( бали): всі елементи масиву рівні ( для всіх );
( балів): всі елементи масиву додатні ( для всіх );
( балів): масив неспадний ( для всіх );
( балів): ;
( балів): ;
( балів): немає додаткових обмежень.