这是一道博弈论 + 贪心构造的问题，核心结论非常简洁：游戏最多进行2步就会结束（Alice操作→Bob直接结束）。

下面我用公式+文字+代码完整讲解标程逻辑，所有公式严格按你的要求排版。

---

一、核心博弈结论（最重要！）

1. Bob 永远不会主动交换元素 如果 Bob 交换，Alice 可以立刻换回去，让 $f(a)$ 变大，这对 Bob 不利。 → Bob 的最优策略：永远在第一次行动直接结束游戏。

2. 游戏只有两种可能结局

   • 情况1：Alice 直接结束游戏 $\boldsymbol{\Rightarrow}$ 答案 = 初始值
   • 情况2：Alice 交换一次 $\boldsymbol{\Rightarrow}$ Bob 结束游戏 → 最终答案 = 这两种情况的最大值

---

二、数学公式定义

1. 初始函数值（不交换）

$$f_0 = \sum_{i=0}^{n-1} \begin{cases} +a[i] & i \text{ 为偶数} \\ -a[i] & i \text{ 为奇数} \end{cases} $$

2. 交换一次的收益

设交换位置 $i$ 和 $j$：

• 代价：$\boldsymbol{|i-j|}$
• 函数值变化：$\boldsymbol{\pm 2(a_i - a_j)}$（由奇偶性决定）

---

三、标程核心推导

1. 只需要考虑两类交换

1. 同奇偶交换 函数值不变，只增加代价。 最优选择：代价最小的同奇偶交换。

2. 异奇偶交换（真正能最大化答案） 交换一个奇数位和一个偶数位，总收益为：

   $$|i-j| + 2\cdot(a_i - a_j)$$

   这是我们要最大化的值。

---

四、标程代码逐行详解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main(){
    int tt;
    cin >> tt;
 
    while(tt--){
        int n;
        cin >> n;
        vector<long long> a(n);
        for(int i = 0; i < n; i++) cin >> a[i];
 
        // 1. 计算初始答案 f0
        ll ans = 0;
        for(int i = 0; i < n; i++){
            if(i % 2) ans -= a[i];
            else ans += a[i];
        }
        ll init = ans; // 保存初始值
 
        // 2. 情况1：最优的【同奇偶交换】
        for(int i = 0; i < n; i++) 
            ans = max(ans, init + i - (i % 2));
 
        // 3. 情况2：最优的【异奇偶交换】（核心）
        ll min_even = LLONG_MAX / 2, min_odd = LLONG_MAX / 2;
        for(int i = 0; i < n; i++){
            if(i % 2){ // 奇数位
                ans = max(init + i + 2*a[i] - min_even, ans);
                min_odd = min(min_odd, i - 2*a[i]);
            }
            else{ // 偶数位
                ans = max(init + i - 2*a[i] - min_odd, ans);
                min_even = min(min_even, i + 2*a[i]);
            }
        }
 
        cout << ans << '\n';
    }
    return 0;
}

---

五、代码三大步骤

1. 计算初始函数值 $\boldsymbol{init}$

直接按定义计算：

• 偶数下标：$+a[i]$
• 奇数下标：$-a[i]$

2. 计算最优「同奇偶交换」

for(int i = 0; i < n; i++) 
    ans = max(ans, init + i - (i%2));

这是代价最小的交换，能带来的最大收益。

3. 计算最优「异奇偶交换」（核心贪心）

我们维护两个最小值：

• min_even：偶数位的最小权值
• min_odd：奇数位的最小权值

单次交换收益公式：

$$\text{gain} = i - 2\cdot a[i] - \text{min\_odd}$$ $$\text{gain} = i + 2\cdot a[i] - \text{min\_even}$$

遍历一次数组即可找到全局最优交换。

---

六、最终答案

$$\boldsymbol{ans = \max(初始值,\ 最优同奇偶交换,\ 最优异奇偶交换)}$$

---

七、时间复杂度

$$O(n) \quad \text{每组测试用例}$$

满足 $n \le 2\times 10^5$ 的限制。

---

八、一句话记住解法

1. Bob 永远直接结束游戏
2. Alice 要么不动，要么换一次最优的
3. 答案 = max(初始值, 最佳单次交换)