Дана последовательность из n целых чисел a1, a2, ..., an. Необходимо найти такую её подпоследовательность, что её сумма нечётна и максимальна по всем таким подпоследовательностям. Гарантируется, что в заданной последовательности найдется подпоследовательность с нечетной суммой.
Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов.
Напишите программу, которая найдет сумму искомой подпоследовательности.
Выходные данные
Выведите сумму искомой подпоследовательности.
Примечание
В первом примере сумма второго и четвертого элементов равна 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
-2 2 -3 1
|
3
|
|
2
|
3
2 -5 -3
|
-1
|