AT_abc162_f [ABC162F] Select Half

题目描述

给定一个长度为 $N$ 的整数序列 $A_1,\ldots,A_N$。

请从中恰好选择 $\left\lfloor \frac{N}{2} \right\rfloor$ 个整数，要求任意两个被选中的位置都不相邻。

请你求出所能得到的选中元素之和的最大可能值。

这里，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

输入格式

输入以如下格式从标准输入读入。

$N$ $A_1$ $...$ $A_N$

输出格式

请输出所能得到的选中元素之和的最大可能值。

输入输出样例 #1

输入 #1

6
1 2 3 4 5 6

输出 #1

12

输入输出样例 #2

输入 #2

5
-1000 -100 -10 0 10

输出 #2

0

输入输出样例 #3

输入 #3

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输出 #3

5000000000

输入输出样例 #4

输入 #4

27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49

输出 #4

295

说明/提示

限制条件

• $2 \leq N \leq 2\times 10^5$
• $|A_i| \leq 10^9$
• 输入均为整数

样例解释 1

选择 $2,4,6$，它们的和为 $12$，这是最大值。

样例解释 2

选择 $-10,10$，它们的和为 $0$，这是最大值。

样例解释 3

请注意防止溢出。

由 ChatGPT 4.1 翻译