Maximum Sum on Even Positions

形式化题目

给定下标从 $0$ 开始的数组 $a$ ，可以选一个连续区间 $[l,r]$ ，将其中的元素顺序反转，也可以不操作。求操作后所有偶数下标位置上的元素之和的最大值。

暴力解法

思路

枚举反转区间，直接计算操作后的偶数位和。

先用不操作时的偶数位和初始化答案。随后枚举所有区间，每次复制原数组、反转选中的区间，再统计偶数位和，取最大值。这样覆盖了所有允许的选择。

brute.cpp 按这个过程实现，适合在小数据上作为核对答案的基线。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-11-04 10:50
 * update_at: 2026-11-04 14:09
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 2005;

ll n;
ll a[MAXN];
ll temp_a[MAXN];

// 暴力求解一个测试用例：枚举所有可能的区间 [l, r] 并反转，统计偶数位之和
void solve() {
    cin >> n;
    for (ll i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 计算初始（不反转）时的偶数位和
    ll max_ans = 0;
    for (ll i = 0; i < n; i += 2) {
        max_ans += a[i];
    }

    // 枚举所有可能的反转区间 [l, r]
    for (ll l = 0; l < n; ++l) {
        for (ll r = l; r < n; ++r) {
            // 复制原数组
            for (ll i = 0; i < n; ++i) {
                temp_a[i] = a[i];
            }
            // 反转区间 [l, r]
            reverse(temp_a + l, temp_a + r + 1);

            // 统计当前偶数位元素之和
            ll cur_sum = 0;
            for (ll i = 0; i < n; i += 2) {
                cur_sum += temp_a[i];
            }
            max_ans = max(max_ans, cur_sum);
        }
    }

    cout << max_ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度

共有 $O(n^2)$ 个区间，每次复制、反转和求和需要 $O(n)$ 时间，总时间复杂度为 $O(n^3)$ ，额外空间复杂度为 $O(n)$ 。

瓶颈

题目允许单组 $n$ 达到 $2\times10^5$ ，不能逐个枚举区间。先看每次重新求和的过程：区间外的元素没有变化，真正需要计算的只有区间内的收益。若能把收益写清楚，就有机会直接寻找收益最大的区间。

正解

思路

按两种起点合并相邻位置，把反转收益转成最大子段和。

奇数长度的区间反转后，元素所在位置的奇偶性不变；偶数长度的区间反转后，奇偶性全部互换，所以收益等于区间内原来的奇数位和减去偶数位和。把相邻两个位置的贡献合并，偶数长度区间就对应连续若干对。按起点奇偶分成两组，各求一次最大子段和，再将最大非负收益加到原来的偶数位和上。

先看反转会让哪些数进入答案。

记原来的偶数位和为 tot。目标只关心一个数是否位于偶数下标，不关心它具体位于哪个偶数下标。因此，分析反转时只需追踪位置的奇偶性。

反转 $[l,r]$ 后，原来位于 $i$ 的元素会移到 $l+r-i$ 。由此分成两种情况：

区间长度为奇数， $l,r$ 同奇偶， $l+r$ 为偶数。新旧位置同奇偶，参与求和的数没有变，收益为 $0$ 。
区间长度为偶数， $l,r$ 异奇偶， $l+r$ 为奇数。原来在奇数位的数全部进入答案，原来在偶数位的数全部退出答案。

所以只需寻找收益最大的偶数长度区间。不操作也能得到零收益。

把一次反转的收益拆到每个位置上。

对于偶数长度的反转区间，奇数位的数要加进来，偶数位的数要减出去。代码用 dif 记录这两类贡献：

\mathrm{dif}[i]= \begin{cases} a_i,&i\text{ 为奇数},\\ -a_i,&i\text{ 为偶数}. \end{cases}

于是，反转一个偶数长度区间的收益，就是这段 dif 的和。问题变成了：在 dif 中找一个和最大的偶数长度子段。

这里还不能直接套最大子段和，因为它可能选中奇数长度的子段。例如 $a=(1,10)$ 时， $\mathrm{dif}=(-1,10)$ 。普通最大子段和会选出单独的 $10$ ，但只反转一个元素毫无收益；真正反转两项的收益是 $10-1=9$ 。

怎样让最大子段和选出的区间一定是偶数长度？

把相邻两项合成一项。之后每选一个新元素，就相当于选了两个原位置，长度限制便自动满足了。

不过，配对方式取决于区间的左端点。例如 $[0,3]$ 要拆成 $(0,1),(2,3)$ ，而 $[1,4]$ 要拆成 $(1,2),(3,4)$ 。因此要保留两套配对。下表按 main.cpp 中的变量名列出它们，每个新元素都是一对位置的贡献之和。

新数组	反转区间的左、右端点	原数组中的配对	每对的收益
`b1`	左端点为奇数，右端点为偶数	$(1,2),(3,4),(5,6),\dots$	$a_1-a_2,\ a_3-a_4,\ a_5-a_6,\dots$
`b2`	左端点为偶数，右端点为奇数	$(0,1),(2,3),(4,5),\dots$	$a_1-a_0,\ a_3-a_2,\ a_5-a_4,\dots$

两组都遵循“奇数位的值减去偶数位的值”。在 b1 中奇数位在左边，在 b2 中奇数位在右边，不能把它们都写成右边减左边。代码统一累加 dif[i-1] + dif[i]，正负号已经由 dif 处理。

这里的配对只是在合并收益，实际执行的仍是整段反转。要用最大子段和，还需要确认这种合并没有遗漏或引入额外选择：

从反转区间到连续子段。 任意偶数长度区间，从左到右每两项分一对，恰好落在 b1 或 b2 的连续若干项中。每对的贡献相加，就是整段反转的收益。
从连续子段到反转区间。 任取 b1 或 b2 的一个非空连续子段，其中各对首尾相接，覆盖一个偶数长度的原数组区间。反转这个区间，就能得到该子段和对应的收益。

因此，在两组数组上分别求最大子段和，就覆盖了所有可能产生收益的反转区间。

模型确定后，用 Kadane 求最大收益。

对任意一组配对数组 $b$ ，令 $dp_j$ 表示以第 $j$ 项结尾的最大非空子段和。处理当前项时，可以从这里重新开始，也可以接在前一个最优子段后面：

dp_j=\max(b_j,\ dp_{j-1}+b_j).

这个转移就是 max_subarray 中对 dp 的更新。遍历时用 best 保存出现过的最大值，并将它初始化为 $0$ ，把不操作的选择也算进去。函数进入循环前令 dp = 0，第一次更新便得到 $b_0$ ；若数组为空，直接返回 best = 0。

最终答案为 tot + max(max_subarray(b1), max_subarray(b2))。

用题面第一组数据串起整个过程。

数组为 $a=(1,7,3,4,7,6,2,9)$ ，原来的偶数位和为 $\mathrm{tot}=1+3+7+2=13$ 。两套配对得到：

b1： $(7-3,\ 4-7,\ 6-2)=(4,-3,4)$ ，最大子段和为 $5$ ，选整段，对应反转原数组的 $[1,6]$ 。
b2： $(7-1,\ 4-3,\ 6-7,\ 9-2)=(6,1,-1,7)$ 。

下面逐项处理 b2。每行列出当前配对的收益、以当前项结尾的 dp，以及目前为止的 best。

对应的原位置	当前收益	`dp`	`best`
$(0,1)$	$6$	$6$	$6$
$(2,3)$	$1$	$7$	$7$
$(4,5)$	$-1$	$6$	$7$
$(6,7)$	$7$	$13$	$13$

中间的 $-1$ 虽然亏损，但保留它可以把前后的收益连成一个区间，所以不能只挑正数相加。b2 的最优选择是整段，对应反转整个原数组，答案为 $13+13=26$ 。

反转后数组为 $(9,2,6,7,4,3,7,1)$ ，偶数位上的数为 $9,6,4,7$ ，和确实是 $26$ 。

代码

C++ 中，tot 保存原答案，dif 保存逐位置贡献，b1、b2 保存两套配对收益。 $n=1$ 时两组都为空，答案为 $a_0$ ； $n=2$ 时只有 b2 中的一项 $a_1-a_0$ ，答案为 $\max(a_0,a_1)$ 。若两组都没有正收益，best 保持为 $0$ ，即不反转。

$a_i$ 最大为 $10^9$ ，累加结果可能超过 32 位整数范围，因此求和、收益和 DP 都使用 long long。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-11-04 10:50
 * update_at: 2026-11-04 15:40
 */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 5;

ll n;
ll a[MAXN]; // 原数组，下标 0 到 n - 1

// 最大子段和 dp（允许空段，返回 >= 0）
// dp[i] = 以 b[i] 结尾的最大子段和
ll max_subarray(vector<ll> &b) {
    ll best = 0;
    ll dp = 0;
    for (ll i = 0; i < (ll)b.size(); ++i) {
        dp = max(b[i], dp + b[i]);
        best = max(best, dp);
    }
    return best;
}

// 求解单个测试用例
void solve() {
    cin >> n;
    for (ll i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 初始状态下所有偶数位置的元素之和
    ll tot = 0;
    for (ll i = 0; i < n; i += 2) {
        tot += a[i];
    }

    // dif[i]：第 i 位对"偶数位和"的贡献变化
    //   i 为奇数（反转后会移到偶数位）：+a[i]
    //   i 为偶数（反转后会被挤走）    ：-a[i]
    // 于是反转偶数长度区间 [l, r] 的收益 = 区间奇数位之和 - 偶数位之和
    //                                   = dif 上的一段子段和
    vector<ll> dif(n);
    for (ll i = 0; i < n; ++i) {
        dif[i] = (i & 1) ? a[i] : -a[i];
    }

    // 反转长度必须是偶数 ⇒ l 与 r 奇偶性相反 ⇒ 区间由连续的"相邻两元素"配对构成
    // 每一对的收益都是 dif[i] + dif[i-1]，也就是 a[i] - a[i-1]（奇数位 - 偶数位）
    // 两种情况只是"右端点 r 的奇偶性"不同：

    // b1：右端点 r 为偶数下标 → 配对 (1,2), (3,4), (5,6)...
    vector<ll> b1;
    for (ll i = 2; i < n; i += 2) {
        b1.push_back(dif[i] + dif[i - 1]);
    }

    // b2：右端点 r 为奇数下标 → 配对 (0,1), (2,3), (4,5)...
    vector<ll> b2;
    for (ll i = 1; i < n; i += 2) {
        b2.push_back(dif[i] + dif[i - 1]);
    }

    // 反转区间必须是若干连续配对，收益就是 b 上的一个连续子段和
    ll max_gain = max(max_subarray(b1), max_subarray(b2));

    cout << tot + max_gain << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Python 实现采用相同的配对方法，用 itertools.accumulate 依次计算 Kadane 的状态。它的 dp 函数在非空数组上可能返回负数，因此在最后用 max(0, g1, g2) 纳入不操作的选择。

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72"""
1. 设定反转的区间为从 [i,j]
2. 那么这个区间的长度一定是偶数长度 否则翻转完之后 奇数位还是奇数位 偶数位还是偶数位
3 4 5
5 4 3


2 3 4 5
5 4 3 2


固定结尾 J 那么我们能得到的最大反转区间是什么呢？

tot +Odd(i,j) - Eeven(i,j)  

所以这里我们要找到一个最大的 i ,是的 Odd(i,j) - Eeven(i,j) 最大

Odd(i,j) = prefix_odd[j] - prefix_odd[i-1]
Eeven(i,j) = prefix_even[j] - prefix_even[i-1]


我又简单地思考了一下

发现无论是以偶数的 J 是以奇数的 J  结尾
翻转完之后 总是把偶数的位置减去 奇数的位置增加
"""

import sys
from functools import reduce
from itertools import accumulate

a = []

# 得到区间最大和
def dp(a:list[int]):
    if len(a) == 0:
        return 0
    f = accumulate(a,lambda x,y :max(x+y,y))
    return max(list(f))

def solve(data):
    global a
    T = next(data)
    while T > 0:
        T-=1
        n = next(data)

        a = [next(data) for _ in range(n)]
        # 所有偶数位置的和
        tot = sum(a[0::2])

        c = [ a[i] if i & 1  else -a[i] for i in range(n)]

        # end pos is Even
        t = [c[i]  + c[i-1] for i in range(2,n,2)]
        g1 = dp(t)


        # end pos is Odd
        t= [c[i]  + c[i-1] for i in range(1,n,2)]
        g2 = dp(t)
        ans = tot + max(0,g1,g2)

        
        print(ans)

    


if __name__ == "__main__":
    data = iter(map(int, sys.stdin.buffer.read().split()))
    solve(data)

复杂度

求原答案、构造贡献和配对数组、运行两次 Kadane，都只需线性扫描。每组时间复杂度为 $O(n)$ ，额外空间复杂度为 $O(n)$ ；所有测试用例合计为 $O(\sum n)$ ，其中 $\sum n\leqslant2\times10^5$ 。

总结

这道题的转化是：先按位置是否计入答案写出反转收益，再通过合并相邻两项，把“只能选偶数长度区间”的限制放进数组表示中。配对完成后，普通最大子段和就能直接处理；两种起点必须都保留，收益始终按原下标的奇数位减偶数位计算。