Игра с удалением чисел
Давайте сыграем в следующую игру. У вас есть
n положительных целых чисел (при этом n — чётное). На каждом ходу вы можете убрать из последовательности число либо с самого начала, либо с самого конца и оставить его себе. Я (компьютер) в свой ход уберу то число, которое больше среди первого и последнего элементов. Если они равны, то я заберу первый из них. Мы будем ходить по очереди, пока список не опустеет.Если вы ходите первым, каков максимальный суммарный результат вы сможете набрать?
Входные данные
В первой строке входных данных содержится одно целое число
n (1 ≤ n ≤ 1000).Во второй строке указаны
n разделённых пробелами чисел (1 ≤ ≤ ).Выходные данные
Программа должна вывести максимальную сумму чисел, которую вы сможете собрать.
Примеры
Входные данные | Выходные данные |
4
3 2 10 4 | 13 |
Пояснение
- Вы берёте первый элемент 3 →
2 10 4
- Компьютер забирает 4 →
2 10
- Вы берёте 10 →
2
- Компьютер забирает 2 ⇒ Вы собрали 3 + 10 = 13
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB